Wat is een volledige grafiek?

Beste antwoord

Bent u bekend met de structuur van een molecuul cyclopropaan? Een cyclopropaan is een alicyclische koolwaterstof die bestaat uit drie koolstofatomen gerangschikt in een ringvormige structuur zoals deze

Bekijk de structuur zorgvuldig. Negeer voorlopig de waterstofatomen en let op de covalente bindingen tussen twee koolstofatomen. Merk op dat elk koolstofatoom is gebonden met elk ander koolstofatoom in een molecuul cyclopropaan. Dit is de basisintuïtie achter een complete grafiek.

Nu een formele definitie:

Een complete graaf die uit n hoekpunten bestaat, is een verbonden graaf zodat er een pad van lengte één bestaat tussen twee hoekpunten van de graaf . Met andere woorden, in een volledige grafiek grenst elk hoekpunt aan de resterende hoekpunten, zodat het aantal randen in de grafiek exact \, \ binom {n} {2}

A een beter voorbeeld van een complete grafiek is \, K\_5 \,

Merk op dat in de bovenstaande grafiek elk hoekpunt is verbonden met alle andere hoekpunten. Daarom is het een complete grafiek.

Antwoord

Verschil tussen grafiek- en boomgegevensstructuur:

Grafiek

1. In grafiek kan er meer dan één pad zijn, dwz de grafiek kan unidirectionele of bidirectionele paden tussen knooppunten hebben.
2. In graph is er niet zon concept van root node.
3. Graph kan zowel loops, circuits als self-loops hebben.
4. In Graph is er niet zon ouder-kindrelatie.
5. Grafieken zijn complexer in vergelijking met bomen omdat het cycli, lussen enz. kan bevatten.
6. Grafiek wordt doorlopen door DFS : diepte Eerste zoekopdracht en in BFS : algoritme voor breedte eerste zoekopdracht.
7. De grafiek kan cyclisch of Acyclisch zijn.
8. Er zijn hoofdzakelijk twee soorten grafieken: gestuurde en niet-gerichte grafieken.
9. Grafiektoepassingen: kleuren van kaarten, een lgoritmen, grafiekkleuren, taakplanning enz.
10. In Graph, nr. van randen is afhankelijk van de grafiek.
11. Grafiek is een netwerkmodel.

Bomen

1. Tree is een speciale vorm van een graaf, dwz minimaal verbonden graaf en met slechts één pad tussen twee hoekpunten.
2. Tree is een speciaal geval waarin een graaf geen lussen, geen circuits en geen self-loops heeft.
3. In de boom is er precies één root knooppunt en elk kind hebben slechts één ouder.
4. In bomen is er een ouder-kindrelatie, dus er kan stroom zijn met richting van boven naar beneden of vice versa.
5. Bomen zijn minder complex dan grafieken omdat ze geen cycli hebben, geen self-loops en toch verbonden zijn.
6. Tree traversal is een soort speciaal geval van traversal van de grafiek. Boom wordt doorkruist in Pre-order , In-order en Post-order (alle drie in DFS of in BFS algoritme)
7. Bomen vallen in de categorie van DAG: Directed Acyclic Graphs is een soort gerichte graaf zonder cycli.
8. Verschillende soorten bomen zijn: Binaire boom , Binaire zoekboom, AVL-boom, Heaps.
9. Boom-toepassingen : sorteren en zoeken zoals Tree Traversal & Binary Search.
10. Tree heeft altijd n-1 randen.
11. Tree is een hiërarchisch model.