momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Asupra unui graf 3-colorabil, planar, hamiltonian (IV)

graf | limbajul R | orar şcolar
2023 jan

Î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)

docerpro | Prev | Next