-
Regulat
-
Complet
Laborator de teoria grafurilor
Un graf este o mulțime de puncte, numite vârfuri, unite prin linii, numite muchii. Desenați unul aici din câteva clicuri, iar laboratorul vă spune ce fel de graf este: din câte componente este format, dacă este arbore, de câte culori are nevoie cel puțin, dacă poate fi desenat dintr-o singură linie, fără a ridica creionul, și multe altele. Faceți clic pe o proprietate pentru a o vedea pe graf, schimbați o muchie și urmăriți cum se schimbă răspunsurile. Faceți clic pe un loc gol pentru a adăuga un vârf. Faceți clic pe un vârf, apoi pe altul, pentru a le uni printr-o muchie; repetați pentru a elimina muchia. Trageți un vârf pentru a-l muta. Comutați clicul pe Șterge și faceți clic pe un vârf sau pe o muchie ca să le ștergeți. Cu un vârf selectat, Delete îl elimină, iar Esc renunță la selecție. Faceți clic pe o proprietate pentru a o vedea pe graf. Exemplu încarcă un graf cunoscut, Graf aleatoriu creează unul nou, Aranjează distanțează vârfurile, iar Complementar unește exact perechile care nu erau unite. Ctrl+Z anulează un pas.
Cum funcționează
- Faceți clic pe un loc gol pentru a adăuga un vârf. Faceți clic pe un vârf, apoi pe altul, pentru a le uni; repetați pentru a elimina muchia. Trageți un vârf pentru a-l muta.
- Citiți proprietățile de sub graf și faceți clic pe una pentru a o afișa: o colorare, cele două părți, un drum eulerian, un arbore parțial, cel mai scurt ciclu sau diametrul.
- Încărcați un exemplu, cum ar fi graful Petersen, creați un graf aleatoriu, luați complementarul sau comutați clicul pe Șterge pentru a șterge vârfuri și muchii.
Ce înseamnă proprietățile
Gradul unui vârf este numărul de muchii care pornesc din el. Un graf este conex când din orice vârf se poate ajunge în oricare altul de-a lungul muchiilor și este arbore când este conex și nu are cicluri. Este bipartit când vârfurile sale se împart în două părți, iar fiecare muchie trece de la o parte la cealaltă, ceea ce se întâmplă exact atunci când nu are niciun ciclu de lungime impară. Numărul cromatic este cel mai mic număr de culori cu care vârfurile vecine pot primi culori diferite. Lungimea celui mai scurt ciclu se numește talia grafului (în engleză girth), iar diametrul este cea mai mare distanță dintre două vârfuri, măsurată în muchii.
Desenat dintr-o singură linie
Un drum eulerian folosește fiecare muchie exact o dată. Leonhard Euler a observat în 1736, pornind de la cele șapte poduri din Königsberg, ce anume îl poate împiedica: de fiecare dată când un drum trece printr-un vârf, folosește două dintre muchiile lui. Așadar, fie toate gradele sunt pare, iar drumul se poate termina unde a început, fie exact două grade sunt impare, iar drumul trebuie să meargă de la unul dintre aceste vârfuri la celălalt. Mai târziu, Carl Hierholzer a demonstrat că această condiție, împreună cu faptul că toate muchiile se află într-o singură componentă, este și suficientă. Încărcați exemplul cu căsuța și găsiți de unde trebuie să înceapă linia.
Întrebări frecvente
Ce este un graf în teoria grafurilor?
O mulțime de puncte, numite vârfuri sau noduri, și linii între unele perechi de puncte, numite muchii. Nu este graficul unei funcții: descrie doar ce este legat de ce. Hărțile rutiere, rețelele sociale, moleculele și rețelele de calculatoare sunt toate grafuri.
Cum se calculează numărul cromatic?
Laboratorul încearcă să coloreze graful cu o culoare, apoi cu două, apoi cu trei și așa mai departe, iar pentru fiecare număr caută prin toate variantele care contează, colorând mereu în continuare vârful ai cărui vecini folosesc deja cele mai multe culori. Primul număr care funcționează este numărul cromatic. Pentru grafurile pe care le puteți desena aici, asta durează cel mult o clipă; la un graf foarte dificil, căutarea se oprește mai devreme, iar valoarea este afișată ca limită superioară.
Când are un graf un drum eulerian?
Când toate muchiile sale se află într-o singură componentă și cel mult două vârfuri au grad impar. Fără vârfuri impare, există un ciclu eulerian care se termină unde începe; cu două, fiecare drum eulerian începe în unul dintre ele și se termină în celălalt. Numărul vârfurilor impare este întotdeauna par, deci nu poate fi niciodată exact unu.
Ce este complementarul unui graf?
Graful cu aceleași vârfuri, ale cărui muchii sunt exact perechile care nu erau unite înainte. Complementarul complementarului este chiar graful de la care ați pornit. De exemplu, complementarul grafului Petersen este 6-regulat, pentru că fiecare vârf era unit cu 3 dintre celelalte 9.
De ce este faimos graful Petersen?
Este un graf mic, cu 10 vârfuri și 15 muchii, care servește drept contraexemplu pentru multe conjecturi optimiste. Fiecare vârf are gradul 3, cel mai scurt ciclu are lungimea 5, oricare două vârfuri sunt la cel mult 2 muchii distanță și nu poate fi desenat fără ca muchiile să se intersecteze. Laboratorul pornește cu el.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor