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

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

graf | limbajul R | orar şcolar
2023 jan

În [2] am ilustrat pe un graf mic un algoritm aproape evident, pentru a găsi (mai degrabă, „manual”) o reprezentare planară (dacă există) pentru un graf hamiltonian. Acum „automatizăm” pe cât se cuvine demersurile acestui algoritm, vizând chiar graful G (cu 92 de vârfuri și 150 de muchii) de la care am plecat în [2]-(I).

Considerăm ciclul hamiltonian CH găsit în [2]:

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)
DP <- 1:92 %>% setNames(CH)

DP mapează CH pe 1..92: DP[as.character(w)] ne va da rangul (locul, sau adâncimea) la care apare vârful w în vectorul CH.

Vom reprezenta CH pe o dreaptă. Rămân de adăugat celelalte 150-91=59 de muchii care unesc vârfuri care nu sunt consecutive în CH; pentru a asigura că nu se intersectează (decât eventual, în capete), ținem seama de adâncimile în CH ale capetelor: de exemplu, dacă DP[u] > DP[u1] și DP[v] < DP[v1], atunci muchiile u--v și u1--v1 pot fi reprezentate de o aceeași parte a dreptei CH, încât să nu se intersecteze.

Vom constitui un tabel d59 (obiect data.frame) care pentru fiecare muchie dintre cele 59, înregistrează capetele și adâncimile în CH ale acestora; în acest scop, mai întâi formulăm o listă care asociază fiecărui vârf din CH, adiacenții acestuia aflați în CH după vârful respectiv și la distanță mai mare ca 1 de acesta:

locs <- map(CH, function(v) {
    rv <- DP[as.character(v)]
    ngb <- neighbors(G, v) %>% as.integer()
    rgb <- ngb[DP[as.character(ngb)] > rv + 1]
    DP[as.character(rgb)] %>% setNames(rgb) %>% sort()
}) %>% setNames(CH) %>% compact()

De exemplu, vârful 88 – al 35-lea din CH, cum ne arată DP["88"] – are trei adiacenți care apar la dreapta sa în CH, anume la adâncimile 39, 42, respectiv 45:

> locs[["88"]]
        58 57 56
        39 42 45 

Fiindcă diferența de nivel între '58' și '88' este mică (39-35=4), intuim că segmentul 88--58 va trebui trasat mai aproape de dreapta de bază CH, față de segmentul 88--57 (pentru care diferența de nivel este 7); probabil, cele trei segmente din nodul comun '88' vor fi de o aceeași parte a dreptei CH, în ordinea 88--58, 88--57 și 88--56 (primul fiind cel mai apropiat, iar ultimul cel mai depărtat dintre cele trei, față de dreapta de bază).

Pe baza acestei liste, putem constitui tabelul anunțat mai sus d59:

d59 <- data.frame(vf = rep(0, 59), adj = rep(0,59), dpt = rep(0,59))
i <- 0
for(v in names(locs)) {
    rgb <- locs[[v]]
    for(j in 1:length(rgb)) {
        d59$vf[i+j] <- v
        d59$adj[i+j] <- as.integer(names(rgb)[j])
        d59$dpt[i+j] <- as.vector(rgb[j])
    }
    i <- i + j
}
d59$dv <- DP[as.character(d59$vf)]
d59$dst <- d59$dpt - d59$dv  # diferența de nivel între capetele fiecărei muchii

Acum am avea de marcat fiecare muchie din d59, indicând în care parte a dreptei CH ar trebui să o reprezentăm astfel încât să nu intersecteze alte muchii din acea parte. Ni s-a părut mai ușor să operăm manual, această marcare: am salvat d59 în format CSV și într-un editor de text, am adăugat coloana "sm" în care am înscris pe rând 0 sau 1, alegând cum descriem mai jos:

vf, adj, dpt, dv, dst, sm
92, 71,  5, 1,  4,  0  # 92--71 acoperă pozițiile 1..5 din CH
92, 73, 86, 1, 85,  0
92, 74, 89, 1, 88,  0
92, 72, 92, 1, 91,  0
70, 60, 36, 2, 34,  1  # 70--60 acoperă pozițiile 2..36 din CH
13, 59, 34, 3, 31,  1
54, 87, 32, 4, 28,  1

Vârfurile 81..92 au în G gradul 5; celelalte vârfuri sunt de grad 3. Vârfului 92 îi corespund în d59 primele 4 muchii: 92--72 care închide ciclul CH și cele trei muchii corespunzătoare adiacenților săi interiori lui CH și la distanță mai mare ca 1, de capătul 92. Am ales să plasăm aceste 4 muchii care peacă din vârful 92 într-o aceeași parte a dreptei – indicată prin 0.

Celelalte vârfuri de grad 5, fiind interioare ciclului CH, le corespund în d59 câte cel mult trei muchii; iar vârfurilor de grad 3 le corespund în d59 câte cel mult o singură muchie (acest aspect de regularitate și explică, ușurința cu care putem marca manual, muchiile).

Muchia 70--60 (care urmează în d59 după cele 4 muchii care pleacă din vârful 92) nu poate sta tot în partea 0 a dreptei CH: ea acoperă intervalul de indecși [2, 36] din CH, care are intersecție nevidă cu intervalul [1, 5] al rangurilor pe care se întinde muchia 92--71 (deci dacă am pune aceste două muchii într-o aceeași parte, ele s-ar întretăia). Prin urmare, pentru muchia 70--60 înscriem în câmpul sm valoarea 1.

Raționăm la fel pentru celelalte muchii și când încheiem, recuperăm d59 și-l împărțim după valorile din câmpul sm:

d59 <- read_csv("d59.csv", col_type="iiiiii")
ld59 <- d59 %>% split(.$sm)
Sus <- ld59[[1]] %>% arrange(dst) # %>% print(n=Inf)
Jos <- ld59[[2]] %>% arrange(dst)

Tabelele Sus și Jos conțin – în ordinea crescătoare a distanțelor în CH dintre capete – muchiile care vor fi trasate în câte o aceeași parte a dreptei de bază CH.

Fiindcă avem de reprezentat pe o dreaptă multe puncte, alegem o înclinare oblică pentru dreapta respectivă; nu vom reprezenta efectiv nodurile, ci doar etichetele acestora din CH și renunțăm să trasăm și segmentele care le unesc consecutiv în CH. Anulăm marginile obișnuite ale ferestrei grafice, stabilim un font monospațial și apoi plotăm prin text() etichetele respective, în puncte ușor distanțate între ele pe oblica respectivă:

opar <- par(mar=c(0,0,0,0), bty="n", xaxt="n", yaxt="n", family="mono", font=2)
pts <- (12 + 1i*10)*(1:92)  # afixele punctelor la care plasăm etichetele
plot(pts, type = "n")  # inițializează fereastra grafică (fără a plota punctele)
text(x = Re(pts), y = Im(pts), label = CH, cex=0.7)

Urmează să trasăm muchiile din seturile Sus și Jos. Vom reprezenta fiecare muchie prin trei segmente de dreaptă înlănțuite: câte unul perpendicular pe oblică, din fiecare capăt și al treilea care este paralel cu oblica, la o distanță proporțională cumva cu valoarea $dst.

Dar întâi introducem două funcții ajutătoare, dat fiind că segments() cere ca parametri abscise și ordonate, iar noi am preferat exprimarea ca numere complexe a punctelor:

draw_segment <- function(z2, z1, ...) {  # uneşte punctele de afixe z1, z2
    segments(Re(z1), Im(z1), Re(z2), Im(z2), ...)
}
draw_segments <- function(list_2z, ...) {
    for(z in list_2z) draw_segment(z[1], z[2], ...)
}

Următoarea funcție va trasa cele trei segmente asociate muchiei (într-o parte sau alta a oblicei, după semnul parametrului h):

draw_path <- function(vf, adj, h, ...) {
    z1 <- pts[DP[as.character(vf)]]  # punctele corespunzătoare capetelor muchiei
    z2 <- pts[DP[as.character(adj)]]
    z11 <- z1 + h*exp(3i*pi/4)  # z1--z11 este perpendicular pe oblică
    z22 <- z2 + h*exp(3i*pi/4)  # lungime=|h|; Sus dacă h>0, Jos dacă h<0
    draw_segments(list(c(z1, z11), c(z2, z22), c(z11, z22)), lwd=0.6, ...)
}

Argumentul "..." permite transmiterea către funcția segments() a unor alți parametri (de exemplu, pentru a colora cumva, segmentele respective).

Secvența următoare trasează efectiv muchiile respective:

for(i in 1:nrow(Sus))
    draw_path(Sus$vf[i], Sus$adj[i], h=5+2.5*Sus$dst[i], col="blue")
for(i in 1:nrow(Jos))
    draw_path(Jos$vf[i], Jos$adj[i], h=-5-2.5*Jos$dst[i], col="red")
par(opar)  # reconstituie parametrii grafici iniţiali

Imaginea rezultată nu încape în întregime, pe ecran (sau pagină) – dar este ușor de verificat că am obținut o reprezentare planară (cam originală, într-adevăr) a grafului G.
Se văd bine simetriile existente în graf, dar pare destul de greu de făcut legătura între reprezentarea obținută mai sus și poliedrul hexecontahedral din care (cum am evidențiat anterior) provine G; totuși, plecând de la vârfurile 81..92 și urmând din aproape în aproape muchii de cele două culori, nu-i greu de găsit cele 12 foliaje de câte 5 pentagoane (caracteristice poliedrului hexecontahedral), pe care le-am evidențiat în [2].

vezi Cărţile mele (de programare)

docerpro | Prev | Next