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

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

graf | limbajul R | orar şcolar
2023 jan

Putem îmbunătăți lizibilitatea redării modificând mai departe, calculul coordonatelor și eventual, mutând în final unele puncte (sperând măcar, că nu stricăm convexitatea indusă de calculul baricentrelor).

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


Prev
Next
ALL (366 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: