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ă.
Un "intermezzo" conjunctural dintr-o carte pe care tocmai am publicat-o, m-a găsit să întreb: Care este la noi, cel mai important și respectiv, cel mai puțin important obiect? — dar m-am găsit să răspund doar sarcastic: cel mai important este Religie
– are o oră pe săptămână, dar la toate clasele din țară; cel mai puțin importante sunt „muzica” și „desenul” – au câte o jumătate de oră pe săptămână și numai la unele clase.
Reluăm întrebarea, încercând să-i dăm un sens: să clasificăm cumva obiectele, după interferențele induse de planul anual de încadrare al școlii. Încadrarea alocă profesori, clase și număr de ore, pentru fiecare disciplină școlară; interferența a două obiecte ar fi dată de numărul de intrări la aceleași clase, ale profesorilor încadrați pe cele două obiecte.
Deci e vorba de clasificarea nodurilor structurate într-o anumită rețea – e drept, foarte subțire față de sistemele complexe vizate de teoria rețelelor.
vezi Cărţile mele (de programare)