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).
Asupra unui graf 3-colorabil, planar, hamiltonian (I)
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".
Centralitatea nodurilor și colorarea "greedy"
Măsurile de centralitate consfințite de "Network science" reflectă mai bine structura internă a rețelei, decât o poate face clasificarea (obișnuită) după gradele nodurilor. Este de așteptat ca rezultatul colorării să fie mai bun dacă abordăm nodurile în ordinea descrescătoare a centralităților, decât dacă le-am aborda în ordinea descrescătoare a gradelor, sau dacă le-am aborda dinamic dar fără a presupune vreo ordine inițială.
vezi Cărţile mele (de programare)