[1] Problema orarului școlar, pe tărâmul limbajului R
[2] Asupra unui graf 3-colorabil, planar, hamiltonian (I-III)
În [2] am reprezentat nodurile ciclului hamiltonian CH
pe o dreaptă; muchiile rămase ale grafului G
unesc puncte neconsecutive ale lui CH
și le-am putut reprezenta deasupra sau dedesubtul dreptei de bază, în așa fel încât liniile corespunzătoare muchiilor dintr-o aceeași parte a dreptei să nu se întretaie între ele. Reprezentarea planară obținută are însă acest inconvenient: nu poate încăpea decent, pe pagină.
Însă CH
considerat în [2] are o proprietate care ne va permite să „rupem” dreapta de bază în două bucăți (ceea ce va condensa reprezentarea planară inițială):
Nodul "60" împarte CH
în două secțiuni, astfel încât muchiile roșii unesc vârfuri ale unei aceleiași secțiuni: „adiacenții roșii” ai nodurilor din secțiunea "92"--"70"--...--"60" aparțin și ei, acestei secțiuni; analog pentru secțiunea mai lungă "12"--"63"--...--"72". Iar majoritatea muchiilor albastre unesc vârfuri dintr-o secțiune cu vârfuri din cealaltă secțiune a lui CH
.
Aceasta înseamnă că am putea descompune dreapta CH
(care nu poate încăpea convenabil pe ecran), într-un fragment vertical pentru secțiunea "92"--"70"--...--"60", continuat cu unul oblic pentru cealaltă secțiune a ciclului CH
– rămânând să montăm pe și între aceste fragmente, celelalte muchii ale lui G
.
Obs. În cazul lui CH
cele două bucăți au lungimile 36 și 56. Probabil că oricare alt ciclu hamiltonian al grafului G
, are proprietatea de „rupere” evidențiată mai sus; ar fi de văzut dacă există unul pentru care cele două secțiuni să aibă lungimi mai apropiate decât în cazul lui CH
.
De observat și acest mic aspect care va trebui îndreptat: din vârful 81 de exemplu, pleacă trei „muchii roșii” și acestea n-ar trebui să se întretaie – ori vedem pe figură că unul dintre cele trei segmente care constituie fiecare muchie este (parțial) comun acestora…
Reluăm ciclul hamiltonian CH
din [2] și separăm la vârful "60", cele două secțiuni:
CH <- c(92, 70, 13, 54, 71, 14, 55, 65, 18, 39, 79, 17, 40, 47, 5, 26, 46, 4, 25, 41, 3, 23, 28, 1, 21, 81, 24, 37, 84, 38, 53, 87, 52, 59, 88, 60, 12, 63, 58, 19, 35, 57, 8, 31, 56, 7, 30, 51, 6, 29, 36, 2, 22, 82, 27, 33, 83, 32, 43, 20, 34, 80, 89, 61, 45, 11, 62, 78, 91, 76, 44, 85, 42, 49, 10, 69, 50, 86, 48, 66, 9, 75, 68, 90, 67, 73, 16, 77, 74, 15, 64, 72) CH1 <- CH[1:36] # vârful "60" este al 36-lea din CH CH2 <- CH[37:92] # a doua secțiune, cu 56 de noduri DP1 <- 1:36 %>% setNames(CH1) DP2 <- 1:56 %>% setNames(CH2)
Prin DP1
și DP2
vom putea identifica locul unui vârf în cadrul primeia și respectiv, celei de-a doua dintre cele două secțiuni ale lui CH
.
Setăm convenabil fereastra grafică; plotăm cele 36 de noduri din CH1
pe verticală, de sus în jos, și cele 56 de noduri din CH2
pe o dreaptă înclinată de jos în sus:
old_par <- par(mar=c(0,0,0,0), family="mono", font=2, bty="n", xaxt="n", yaxt="n") Pt1 <- 1i*17*(36:1) # punctele asociate nodurilor din CH1 Pt2 <- 16 + (12 + 1i*11)*(1:56) # punctele asociate nodurilor din CH2 plot(0, type = "n", xlim=c(-60, 760), ylim=c(20, 600)) text(x = Re(Pt1), y = Im(Pt1), label = CH1, cex=0.75) text(x = Re(Pt2), y = Im(Pt2), label = CH2, cex=0.75)
Bineînțeles că au fost necesare câteva experimente, pentru a seta cât mai convenabil dimensiunile axelor și pasul punctelor.
Preluăm din [2] fișierul "d59.csv
", în care specificam locurile în CH
(și distanța dintre locuri) pentru capetele fiecăreia dintre cele 59 de muchii ale lui G
rămase în afara ciclului CH
și totodată, prin câmpul sm
repartizam muchiile respective de o parte sau alta a „dreptei” CH
(încât cele aflate de o aceeași parte să fie disjuncte între ele); acum extindem tabelul respectiv cu punctele complexe prin care să trasăm muchiile respective (urmând să le calculăm în fiecare caz) și împărțim tabelul după secțiunea în care se află capetele muchiilor:
d59 <- read_csv("d59.csv", col_type="iiiiii") %>% select(vf, adj, dst, sm) %>% arrange(dst) %>% mutate(z1=1i, z2=1i, z11=1i, z22=1i) V1 <- d59 %>% filter(vf %in% CH1 & adj %in% CH1) %>% mutate(z1 = Pt1[DP1[as.character(vf)]], z2 = Pt1[DP1[as.character(adj)]]) V10 <- V1 %>% filter(sm == 0) %>% select(-sm) # red: 92--71 V11 <- V1 %>% filter(sm == 1) %>% select(-sm) # blue V2 <- d59 %>% filter(vf %in% CH2 & adj %in% CH2) %>% mutate(z1 = Pt2[DP2[as.character(vf)]], z2 = Pt2[DP2[as.character(adj)]]) V20 <- V2 %>% filter(sm == 0) %>% select(-sm) #blue V21 <- V2 %>% filter(sm == 1) %>% select(-sm) #red V3 <- d59 %>% filter(vf %in% CH1 & adj %in% CH2) %>% # (au sm = 0) select(-sm) %>% # green mutate(z1 = Pt1[DP1[as.character(vf)]], z2 = Pt2[DP2[as.character(adj)]])
Reprezentăm fiecare muchie dintre cele 59 prin câte trei segmente îmbinate; redăm aici numai secvența prin care instrumentăm trasarea muchiilor între vârfuri aflate ambele în CH1
:
V11 <- V11 %>% mutate( dst = 25*dst/(max(dst) - min(dst)), # normalizăm distanțele h = 6 + 2.7*dst, # depărtăm liniile față de linia de bază z11 = z1 + h*exp(1i*pi), # îmbinările celor 3 segmente z22 = z2 + h*exp(1i*pi)) print(V11) # afișăm pentru a vedea ce ajustări ar fi de făcut la capetele segmentelor V11$z22[1] <- V11$z22[1] + 10i # ajustează muchia 23--81 V11$z22[2] <- V11$z22[2] + 5i # ajustează muchia 25--81 V11$z22[5] <- V11$z22[5] + 7i # înclină puțin, 40--84 V11$z22[8] <- V11$z22[8] + 7i # înclină puțin, 55--87 for(i in 1:nrow(V11)) # trasează muchiile (prin draw_segments() din [2]) draw_segments(list(c(V11$z1[i], V11$z11[i]), # z1--z11 c(V11$z11[i], V11$z22[i]), # z11--z22 c(V11$z22[i],V11$z2[i])), col="blue", lwd=0.6) # z22--z2
Procedăm analog, pentru V10
, V21
, V20
și V3
– obținând în final:
Ciclul hamiltonian CH
este marcat prin "magenta"; dintre celelalte 59 de muchii, cele marcate prin "red" sau "blue", au fost trasate într-o parte sau alta a fiecăreia dintre secțiunile CH1
și CH2
, iar cele "green" leagă noduri din CH1
cu noduri din CH2
– asigurând că oricare două muchii nu se întretaie decât cel mult într-unul dintre capete.
Avem deci o reprezentare planară a grafului (hexecontahedral) G
, care de data aceasta (spre deosebire de reprezentarea din [2]) se încadrează perfect în pagină.
Lăsăm deschise, două sau trei chestiuni:
Dacă am inscripționa vârfurile poliedrului hexecontahedral conform ciclului hamiltonian CH
, ce semnificație ar avea „povârnișurile” CH1
și CH2
?
Ciclurile hamiltoniene ale lui G
diferite de CH
admit și ele, o fragmentare la un anumit vârf, precum cea evidențiată mai sus la vârful "60" pentru CH
?
Oare orice graf poliedral care este hamiltonian, poate fi reprezentat planar fragmentând ca mai sus un ciclu hamiltonian al său? (poate, numai dacă este și 3-colorabil?)
vezi Cărţile mele (de programare)