Asupra unui graf 3-colorabil, planar, hamiltonian (VI)
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)
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)
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)
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)
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).
vezi Cărţile mele (de programare)