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

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

Centralitatea nodurilor și colorarea "greedy"

graf | limbajul R | orar şcolar
2022 dec

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

Clasificare după interferențe

graf | limbajul R | orar şcolar
2022 nov

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.


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