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

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

graf | limbajul R | orar şcolar
2023 jan

Pentru scheletele poliedrale se cuvine să dăm reprezentări plane convexe, evidențiind cum putem, fiecare față. Vom modela – în două moduri – o idee clasică (W. T. Tutte – "How to draw a graph"): fixăm nodurile ciclului CH[1:5] în vârfurile unui pentagon convex și plasăm fiecare dintre vârfurile rămase, în baricentrul adiacenților săi.

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

graf | limbajul R | orar şcolar
2023 jan

Putem descompune un ciclu hamiltonian al grafului hexecontahedral în două fragmente, astfel încât montând celelalte muchii pe sau între aceste fragmente să obținem o reprezentare planară care și încape decent în pagină.

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

graf | limbajul R | orar şcolar
2023 jan

Comparând pozițiile vârfurilor și ale adiacenților acestora, în cadrul unui ciclu hamiltonian – obținem ușor o reprezentare planară a grafului hexecontahedron (însă… nu încape complet pe ecran sau pagină).

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

C++11 | graf | limbajul R | orar şcolar
2022 dec

Metoda obișnuită pentru a găsi un ciclu hamiltonian folosește "bactracking" (și ne amintim de C++11 sau acum, C++17). Dar prin "Logical Analysis of Data", putem evita pierderea de timp implicată de reluările specifice metodei "backtracking" și putem rezolva eficient o chestiune chiar mai generală: să găsim un subgraf care să fie izomorf unuia dat ca „șablon” (dacă șablonul este un ciclu conținând toate vârfurile – atunci un subgraf izomorf acestuia este un ciclu hamiltonian al grafului respectiv).

Evidențiind că graful este hamiltonian – avem imediat și o metodă foarte simplă ca idee, de a obține o reprezentare planară (sau de a deduce că graful respectiv nu este un graf planar).

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

graf | limbajul R | orar şcolar
2022 dec

Am testat un algoritm de colorare uniformă (cam același număr de noduri pe fiecare culoare) și pe un graf „mare” (n=92, m=150), fără a-i vedea inițial vreo semnificație; acum stabilim că este format din 60 de cicluri care trec câte cinci, prin câte unul dintre cele 12 vârfuri de grad 5 – deci este asociat unui poliedru cu 60 de fețe pentagonale congruente, "pentagonal hexecontahedron".


Prev
Next
ALL (385 titluri)

vezi Cărţile mele (de programare)

despre acesta ~ Home
(sau https://vlad.bazon.net/

Factoriale | Graficul funcţiilor

PGN browser | chess JS engine

Load

in /slightchess

/slightchess

626 partide analizate cu Crafty

(R) Computer Art | Decoraţiuni

Aplicaţii şcolare (javaScript)

Sinteze: