Nejlepší odpověď
Znáte strukturu molekuly cyklopropanu? Cyklopropan je alicyklický uhlovodík skládající se ze tří atomů uhlíku uspořádaných do kruhové struktury, jako je tato.
Pozorně sledujte strukturu. Prozatím ignorujte atomy vodíku a všimněte si kovalentních vazeb mezi kterýmikoli dvěma atomy uhlíku. Všimněte si, že každý atom uhlíku je spojen s každým dalším atomem uhlíku v molekule cyklopropanu. Toto je základní intuice za úplným grafem.
Nyní formální definice:
Kompletní graf skládající se z n vrcholů je propojený graf tak, že mezi libovolnými dvěma vrcholy grafu existuje cesta délky jedna. . Jinými slovy, v úplném grafu každý vrchol sousedí se zbývajícími vrcholy, takže počet hran v grafu je přesně \, \ binom {n} {2}
A lepším příkladem úplného grafu je \, K\_5 \,
Všimněte si, že ve výše uvedeném grafu je každý vrchol spojen s všechny ostatní vrcholy. Jedná se tedy o kompletní graf.
Odpověď
Rozdíl mezi grafem a stromovou datovou strukturou:
Graf
- v graf může existovat více než jedna cesta, tj. graf může mít jednosměrné nebo obousměrné cesty mezi uzly.
- V grafu neexistuje žádný takový koncept kořenový uzel.
- Graf může mít smyčky, obvody a může také mít vlastní smyčky.
- V Graphu neexistuje žádný takový vztah rodič-dítě.
- Grafy jsou ve srovnání se stromy složitější, protože mohou obsahovat cykly, smyčky atd.
- Po grafu prochází DFS : hloubka First Search a v BFS : Šířka algoritmu First Search.
- Graf může být cyklický nebo acyklický.
- Existují hlavně dva typy grafů: Directed and Undirected graphs.
- Graph applications: Coloring of maps, a lgoritmy, zbarvení grafu, plánování úloh atd.
- V grafu č. hran závisí na grafu.
- Graf je síťový model.
Stromy
- Strom je speciální forma grafu, tj. minimálně spojený graf, který má pouze jednu cestu mezi dvěma vrcholy.
- Strom je speciální případ grafu, který nemá žádné smyčky, žádné obvody a žádné smyčky.
- Ve stromu je přesně jeden kořen uzel a každé dítě má pouze jednoho rodiče.
- Ve stromech existuje vztah rodič-dítě, takže tok může být tam se směrem shora dolů nebo naopak.
- Stromy jsou méně složité než grafy, protože nemají cykly, samy smyčky a jsou stále připojeny.
- Traverz stromů je druh zvláštního případu traversalu grafu. Strom je procházen v předobjednávce , v pořádku a Post-Order (všechny tři v DFS nebo v BFS algorithm)
- Stromy patří do kategorie DAG: Directed Acyclic Graphs je druh orientovaného grafu, který nemá žádné cykly.
- Různé typy stromů jsou: Binární strom , Binární vyhledávací strom, strom AVL, hromady.
- Stromové aplikace : třídění a vyhledávání jako procházení stromu a binární vyhledávání.
- Strom má vždy n-1 hrany.
- Strom je hierarchický model.