O colorare uniformă

În [2] (plecând de la [1]) am formulat un algoritm de colorare de tip "greedy", bazat pe ordonarea prealabilă a vârfurilor după centralitate (a vedea igraph::eigen_centrality()); avantajul față de algoritmii obișnuiți (v. igraph::greedy_vertex_coloring()) constă în faptul că distribuția pe vârfuri a culorilor este (mai) uniformă.
Reluăm graful pe care-l alesesem în [2] – fără a-i fi descoperit vreo semnificație – pentru a „testa” (și a ilustra) greedy_color_by_centrality():

library(tidyverse)
library(igraph)
A <- read.table("graph_1257.mat", sep=" ") %>% as.matrix()
G <- graph_from_adjacency_matrix(A, mode="undirected") %>%
     greedy_color_by_centrality()  # v. [2]
coords <- layout_with_dh(G)  # reprezentare grafică a grafului
colrs <- c("gold", "green", "tomato")
V(G)$color <- colrs[V(G)$color]
lbs <- ifelse(degree(G) == 5, "black", "white")  # marchează vârfurile de grad 5
E(G)$color <- "gray70"  # evidențiază un ciclu al grafului (1-27-33-83-28)
E(G, path = c("V1", "V27", "V33", "V83", "V28", "V1"))$color <- "blue"
plot(G, layout = coords, vertex.size=5, vertex.label="", vertex.frame.color = lbs)
tcol <- t(table(V(G)$color))  # distribuția culorilor
legend("left", legend = tcol, pch=21, title="V(G)", 
        pt.bg = colrs, pt.cex=1, cex=.8, bty="n", ncol=1)

Distribuția culorilor este (32, 30, 30) – în timp ce prin greedy_vertex_coloring() rezulta mereu o distribuție neuniformă (și cu 4 culori, nu 3), de exemplu (1, 27, 35, 29).

Preluasem acest graf (prin matricea de adiacență) de la [3]; G este un graf planar, 3-colorabil, hamiltonian – v. [3], pentru ID=1257 – cu 92 de vârfuri și 150 de muchii.
Avem 12 vârfuri de grad 5, evidențiate pe imaginea de mai sus prin vertex.frame.color (celelalte au gradul 3 și au fost plotate fără "border"); anticipând cele de mai jos, am evidențiat și un ciclu al grafului, marcându-i muchiile cu "blue".
În acest moment nu este relevantă, etichetarea nodurile (prin 1..92).

Coordonatele asociate vârfurilor au rezultat prin layout_with_dh(); cam toate funcțiile igraph::layout_... produc coordonatele prin anumiți algoritmi de optimizare, vizând criterii de poziționare cât mai clară (dar compactă) a nodurilor (între ele și față de legături) și eventual, reducând numărul intersecțiilor de muchii (dar fără a viza o reprezentare planară).

Încercăm acum să descoperim de unde se trage graful G și convingându-ne cumva că este planar, să vedem cum l-am reprezenta grafic ca atare (fără intersecții de muchii și – dacă devine relevant – etichetând nodurile).

Topologia grafului

Mai întâi, să depistăm vârfurile de grad 5:

> V(G)[degree(G) == 5]
+ 12/92 vertices, named, from b422180:
 [1] V81 V82 V83 V84 V85 V86 V87 V88 V89 V90 V91 V92  # 81..92

Pentru a găsi ciclurile care trec prin unul dintre aceste 12 vârfuri (precum cel marcat mai sus cu "blue") am putea instrumenta o ”parcurgere în adâncime” (v. igraph::dfs()) plecând din vârful respectiv; dar dacă vrem să obținem toate ciclurile (indiferent de lungime) – este mai simplu (dar interesant) să ținem seama de faptul că un ciclu oarecare este izomorf (doar că, în mai multe moduri) unui graf „circular”:

find_cycles <- function(Graph, k) {
  Ring <- graph.ring(k)  # graf circular 1--2--3--...--k--1
  subgraph_isomorphisms(Ring, Graph)  # ciclurile de lungime k, ale grafului dat
}

Pentru k=3 sau k=4, find_cycles(G, k) ne dă câte o listă vidă – deci G nu are cicluri de lungime 3, sau 4. În schimb, cu k=5 găsim 600 de subgrafuri care corespund unor cicluri de lungime 5 (unele reprezintă un același ciclu al lui G):

Cy <- find_cycles(G, 5)  # print(str(Cy))
    List of 600
     $ : 'igraph.vs' Named int [1:5] 1 28 83 33 27
      ..- (*, "names")= chr [1:5] "V1" "V28" "V83" "V33" ...
      ..- # ETC.
    $ : 'igraph.vs' Named int [1:5] 1 28 23 81 21
      ..- attr(*, "names")= chr [1:5] "V1" "V28" "V23" "V81" ...
    # ETC.

Câte 10 dintre cele 600 de subgrafuri din lista Cy, corespund unui aceluiași ciclu (de lungime 5) al lui G – fiindcă un ciclu poate fi parcurs plecând din oricare vârf al său, fie în sens orar, fie în sens antiorar. Prin urmare G are exact 60 de cicluri distincte, toate de lungime 5.

Obs. Găsim și cicluri de lungime k ≥ 8, iar find_cycles(G, 92) ne-ar da ciclurile hamiltoniene…; dar ideea de a găsi ciclurile prin subgraph_isomorphisms() este practicabilă numai pentru lungimi rezonabil de mici. Iar isomorphic(G, graph.ring(92)) ne dă imediat răspunsul "FALSE" – contrazicând [3]…

Să listăm un set de asemenea 10 subgrafuri (dintre cele 600), asociate unui aceluiași ciclu:

> g1 <- Cy[[1]]  # [1] V1 V28 V83 V33 V27 (1 28 83 33 27)
> for(i in 2:600) if(setequal(g1, Cy[[i]])) print(as.vector(Cy[[i]]))
        [1]  1 27 33 83 28
        [1] 27  1 28 83 33
        [1] 27 33 83 28  1
        [1] 28 83 33 27  1
        [1] 28  1 27 33 83
        [1] 33 27  1 28 83
        [1] 33 83 28  1 27
        [1] 83 33 27  1 28
        [1] 83 28  1 27 33

Să observăm că în cele 10 subgrafuri corespunzătoare unui aceluiași ciclu, se află un singur vârf care în G are gradul 5 (vârful 83, în cazul setului redat mai sus). Cu alte cuvinte, cele 60 de cicluri ale lui G trec câte cinci, prin câte unul dintre cele 12 vârfuri de grad 5 (și ar fi suficient să dăm aceste 60 de cicluri, pentru a constitui graful G).

Dintre cele câte 10 subgrafuri identice ca mulțime de vârfuri, păstrăm unul dintre cele două care au ca prim vârf, un vârf care în G are gradul 5; de exemplu, pentru cele 10 subgrafuri redate mai sus am avea de ales între (83,33,27,1,28) și (83,28,1,27,33) și să observăm că acestea două (egale ca mulțime de vârfuri) diferă prin sensul de parcurgere (unul corespunde sensului orar, celălalt sensului antiorar). Probabil că pentru reprezentarea grafică ar fi important să alegem unul dintre cele două în așa fel încât să avem un același sens de parcurgere, pentru toate cele 60 de cicluri distincte rezultate…

Deocamdată, să extragem din Cy acele câte două subgrafuri cu aceeași mulțime de vârfuri, având ca vârf "1" câte unul dintre cele 12 vârfuri de grad 5 ale lui G:

Dy <- map(Cy, function(G) as.vector(G)) %>%
      list2DF(.) %>% t(.)  %>%
      as.data.frame(.) %>%
      filter(V1 >= 81) %>%  # reține subgrafurile în care vârful '1' are în G gradul 5 
      "rownames<-"(NULL)
print(Dy[1:10, ])
             V1 V2 V3 V4 V5  # numele de vârfuri în cele 120 de grafuri din Dy
        (1)  81 26 46  4 25
        (2)  81 26  5 37 24
        (3)  81 25  4 46 26
        (4)  81 25 41  3 23
        (5)  81 24  2 22 21
        (6)  81 24 37  5 26
        (7)  81 23  3 41 25
        (8)  81 23 28  1 21
        (9)  81 21  1 28 23
        (10) 81 21 22  2 24

Am afișat vârfurile subgrafurilor (1)..(10) care au ca prim vârf, vârful 81 al grafului G (subgrafuri corespunzătoare câte două, celor 5 cicluri din G care trec prin V81) și am boldat cumva cele 5 cicluri distincte două câte două, pe care le alegem astfel: dintre subgrafurile cu aceeași mulțime de vârfuri (1) și (3), alegem (1); apoi, alegem (4) fiindcă vârful 25 urmează după 81 și în (1) și în (4) – încât ciclurile distincte (1) și (4) vor putea fi parcurse (sau… desenate) într-un același sens; apoi, alegem (8) fiindcă vârful 23 urmează după 81 și în (4) și în (8) – deci (4) și (8) pot fi trasate într-un același sens; ș.a.m.d.
Traseul rezultat "81 26 .. 25 81 25 .. 23 81 23 .. 21 81 21 .. 24 81 24 .. 26 81" acoperă cele 5 cicluri care au nodul comun 81 și poate fi trasat păstrând un același sens (de exemplu, cel antiorar), trecând de două ori prin câte o aceeași muchie dintre cele 5 incidente vârfului 81.

La fel stau lucrurile pentru ciclurile care trec câte 5 prin fiecare dintre celelalte vârfuri de grad 5 ale lui G – numai că alegerea descrisă mai sus diferă în privința indecșilor.
Instrumentăm procedeul pe care tocmai l-am descris, astfel:

lDy <- Dy %>% split(.$V1)
Sy <- map_dfr(lDy, function(H) {
         R <- matrix(0, nrow=5, ncol=5, byrow=TRUE) %>% as.data.frame()
         R[1, ] <- H[1, ]  # păstrăm primul dintre cele 10 cicluri (apoi alegem)
         i <- 1
         repeat {
             vf <- as.vector(R[i, ])
             HH <- H[H$V2 == vf[5], ]  # cele două cicluri între care avem de ales
             i <- i + 1
             if(i > 5) break
             R[i, ] <- if(setequal(vf, as.vector(HH[1, ]))) HH[2, ] else HH[1, ]
         }
         R
})

Prin split() am împărțit cele 120 de cicluri din setul Dy în 12 părți de câte 10 cicluri care încep fiecare dintr-un același vârf 81..92. Pentru fiecare parte H (din lista lDy astfel rezultată), am considerat un „tabel” R (obiect de clasă data.frame) cu 5 linii și 5 coloane, în care înscriem cele 5 cicluri pe care le alegem pe rând din H: inițial, înscriem în R primul ciclu din H – apoi, selectăm cele două cicluri din H care au pe locul doi același vârf ca vârful ultim al ciclului tocmai înscris în R și dintre acestea două îl alegem și îl adăugăm în R pe cel diferit ca mulțime de vârfuri, de ultimul înscris.
Prin map_dfr() am reunit cele 12 tabele R, rezultând tabelul Sy cu 60 de linii pe care-l redăm aici astfel (prin programul pr din pachetul //www.gnu.org/software/coreutils):

V1 V2 V3 V4 V5  V1 V2 V3 V4 V5  V1 V2 V3 V4 V5  V1 V2 V3 V4 V5  V1 V2 V3 V4 V5  V1 V2 V3 V4 V5
81 26 46  4 25	83 34 80 19 35	85 44 76 11 45	87 54 71 14 55	89 64 72 12 63	91 76 44 10 69
81 25 41  3 23	83 35 57  8 33	85 45 61 20 43	87 55 65 18 53	89 63 58 19 80	91 69 50  9 75
81 23 28  1 21	83 33 27  1 28	85 43 32  3 41	87 53 38  6 51	89 80 34 20 61	91 75 68 16 77
81 21 22  2 24	83 28 23  3 32	85 41 25  4 42	87 51 30  7 52	89 61 45 11 62	91 77 74 15 78
81 24 37  5 26	83 32 43 20 34	85 42 49 10 44	87 52 59 13 54	89 62 78 15 64	91 78 62 11 76
82 31 56  7 30	84 39 79 17 40	86 50  9 66 48	88 60 70 13 59	90 67 14 55 65	92 74 77 16 73
82 30 51  6 29	84 40 47  5 37	86 48 17 40 47	88 59 52  7 56	90 65 18 39 79	92 73 67 14 71
82 29 36  2 22	84 37 24  2 36	86 47  5 26 46	88 56 31  8 57	90 79 17 48 66	92 71 54 13 70
82 22 21  1 27	84 36 29  6 38	86 46  4 42 49	88 57 35 19 58	90 66  9 75 68	92 70 60 12 72
82 27 33  8 31	84 38 53 18 39	86 49 10 69 50	88 58 63 12 60	90 68 16 73 67	92 72 64 15 74

Sy conține cele 60 de cicluri distincte, de lungime 5, ale lui G; acestea trec câte cinci, prin câte unul dintre cele 12 vârfuri de grad 5 și împreună – conțin toate vârfurile grafului.
Observăm că putem îmbina porțiuni ale unora dintre acestea, pentru a obține cicluri de lungime cel puțin 8; de exemplu, de pe ciclurile prin 92 și respectiv 90 obținem un ciclu de lungime 15: 92 70 13 54 71 14--55 65 18 39 79 90 68 16 73--92.

Plotarea ciclurilor

Să considerăm cele 5 cicluri (V1, V2, V3, V4, V5) care trec printr-un același nod V1 (=81..92) de grad 5; trasăm un pentagon regulat cu centrul în V1 și în vârfurile acestuia plasăm nodurile V2 (și implicit, V5 – coincident cu V2 din ciclul de rang următor); apoi mărim convenabil raza și pe noul cerc, plasăm V3 și V4 „între” câte două noduri V2 consecutive; în final trasăm segmentele corespunzătoare ciclurilor respective:

xc <- 30  # (60, dacă vrem o imagine mai mare)
V1 <- xc*(1 + 1i)  # coordonatele (x,y) pentru nodul V1
k <- 0:4  # pentru a viza vârfurile ciclului
V2 <- V1 + 20*exp(2i*k*pi/5)  # vârfurile pentagonului regulat de centru V1
V3 <- V1 + 30*exp(2i*(3*k + 1)*pi/15)
V4 <- V1 + 30*exp(2i*(3*k + 2)*pi/15)
nodes <- c(V1, V2, V3, V4)  
nodes_name <- function(v1) {  # etichetează foliajul centrat în V1
    sy5 <- Sy[Sy[, 1] == v1, ]  # cele 5 cicluri prin vârful V1
    as.character(c(v1, sy5[, 2:4] %>% as.vector() %>% unlist()))
}
foliage <- function(v1) {
    plot(0, type="n", xlim=c(0, 2*xc), ylim=c(0, 2*xc), asp=1,
         family="mono", font=2, xaxt="n", yaxt="n", bty="n")
    col <- "gray70"
    segments(Re(V1), Im(V1), Re(V2), Im(V2), col=col)  # razele V1--V2
    segments(x0=c(Re(V2), Re(V3)), y0=c(Im(V2), Im(V3)),
             x1=c(Re(V3), Re(V4)), y1=c(Im(V3), Im(V4)), col=col)  # muchiile V2--V3
    up <- c(V2[2:5], V2[1])  # circulează V2 cu o poziție
    segments(Re(V4), Im(V4), Re(up), Im(up), col=col)  # muchiile V4--V2
    text(nodes, labels = nodes_name(v1))
}
par(mfrow = c(3, 4))  # pentru a plota 3 paragrafe de câte 4 foliaje
for(v in 81:92)
    foliage(v)
par(mfrow = c(1, 1))
savePlot("81-92.png")

Subliniem că am evitat să amestecăm constituirea și respectiv, plotarea datelor; dacă am fi definit vectorii V1..V4 în interiorul funcției foliaje(), atunci în toate apelurile care ne-au dat panoul grafic al celor 12 foliaje redat mai sus, s-ar fi calculat aceleași coordonate de vârfuri: V1 păstrează coordonatele centrului, mereu (30, 30); în V2 se determină plecând de la axa orizontală, coordonatele vârfurilor pentagonului regulat de centru V1 – constante de la un apel la altul; analog avem pentru V3 și V4.

Un „joculeț” fără soluție…

Acum se pare că ajungem manual, la o reprezentare planară a lui G: decupăm fiecare „foliaj”, apoi identificăm câte două foliaje care să aibă un triplet de vârfuri consecutive în comun, rotim unul dintre ele și apoi le alipim după cele două muchii ale tripletului respectiv. De exemplu, primele foliaje (81) și (82) dintre cele redate mai sus, au în comun tripletul 1--21--22; n-avem decât să „sucim” cumva (82) și să-l montăm astfel încât unghiul 1--21--22 al său (deschis spre interior) să „intre” în cel omonim (deschis spre exterior) din (81).

Nu prea ne interesează o construcție bazată pe forfecuță…
Dar să observăm că rezultă un „joculeț” instructiv: oferă copiilor un set de 12 foliaje cu vârfurile marcate cum am redat mai sus, cerându-le să le asambleze astfel încât oricare două vecine să-și suprapună trei vârfuri omonime.

Unii copii vor sesiza că (81) și (82) au nu trei, ci chiar 4 vârfuri comune (1--21--22--2); apoi că, dacă îmbinăm (81) și (82) după traseul comun lor, atunci foliajul extins obținut va avea în comun cu (83) un traseu zig-zag cam lung: 8--33--27--1--28--23--3… Dacă au învățat deja cuvântul „imposibil”, atunci probabil că în acest moment îl vor și aplica joculețului oferit și vor manifesta foarte multă dezamăgire.

Să insistăm totuși: se cere să asamblați cartonașele, încât (mereu) vârfurile omonime să se suprapună. Poate că vreun copil (și va fi momentul de a discuta cu părinții despre viitorul lui) va învârti cumva foliajele și până la urmă le va și îndoi după pentagoanele conținute (scoțându-le din plan) – reușind să asambleze un poliedru care are ca fețe pentagoanele din foliajele prezentate, alipite după vârfurile comune…
[Obs. Joculețele practicate prin grădinițe ar trebui să aibă și alt sens decât acela de a-i ține pe copii plăcut ocupați… inclusiv, sensul de a descoperi și semnala potențialitățile adevărate ale copiilor, care de atâtea ori rămân ascunse și sunt ulterior falsificate și anihilate de un „sistem” de învățământ bazat pe dresaj, pe reguli și pe memoratoare de formule.]

Este adevărat însă – și nu-i greu de verificat – că pentru a asambla perfect poliedrul respectiv este necesar ca pentagonul din care s-au generat cele 12 foliaje să aibă o anumită formă; pentagonul imaginat mai sus așază un triunghi isoscel deasupra unui trapez isoscel, dar fără a proporționa „corect” latura mai lungă față de aceea mai scurtă și fără a prevedea corect unghiul de la baza trapezului – încât asamblarea ca poliedru nu va reuși decât doar aproximativ.

Poliedrul respectiv (cu 60 de fețe pentagonale congruente), are numele (sugerat și în [3]) pentagonal hexecontahedron; se poate găsi o imagine a lui în multe locații Web, împreună eventual cu o reprezentare prin cele 12 „foliaje” (dar fără etichete pe vârfuri, cum avem mai sus) – comercializate uneori sub formă de cartonașe sau plăcuțe metalice, împreună cu dispozitive simple necesare asamblării în spațiu, a acestora.

Mai departe planul nostru ar fi acesta: să găsim un ciclu hamiltonian al lui G (amintindu-ne că am mai făcut așa ceva prin 2009, vizând graful săriturilor calului pe tabla de șah N×N – deci pentru N=10, un graf comparabil ca mărime cu G); apoi, să încercăm să ne folosim de ciclul hamiltonian respectiv, pentru a ajunge la o reprezentare planară a lui G.
Desigur, planurile inițiale se vor putea schimba în timp, după cum eșuează o direcție sau alta…; dar numai așa, vom putea considera că am închis subiectul grafului 1257.