Hva er en fullstendig graf?

Beste svaret

Er du kjent med strukturen til et molekyl av cyklopropan? Et cyklopropan er et alisyklisk hydrokarbon som består av tre karbonatomer anordnet i en ringstruktur som denne

Observer strukturen nøye. Ignorer hydrogenatomene for nå, og bare legg merke til de kovalente bindingene mellom to karbonatomer. Vær oppmerksom på at hvert karbonatom er bundet til hvert annet karbonatom i et molekyl av cyklopropan. Dette er den grunnleggende intuisjonen bak en komplett graf.

Nå en formell definisjon:

En komplett graf bestående av n hjørner er en sammenkoblet graf slik at det eksisterer en sti med lengde en mellom de to hjørnene i grafen . Med andre ord, i en komplett graf, ligger hver toppunkt ved siden av de gjenværende toppunktene slik at antall kanter i grafen er nøyaktig \, \ binom {n} {2}

A bedre eksempel på en komplett graf er \, K\_5 \,

Vær oppmerksom på at i toppen ovenfor er hvert toppunkt knyttet til alle andre hjørner. Derfor er det en fullstendig graf.

Svar

Forskjell mellom graf og tre Datastruktur:

Graf

1. I graf kan det være mer enn en bane, dvs. grafen kan ha enveis eller toveis stier mellom noder.
2. I grafen er det ikke noe slikt begrep rot node.
3. Graf kan ha sløyfer, kretser så vel som kan ha selvsløyfer.
4. I graf er det ikke noe slikt foreldrebarnsforhold.
5. Grafer er mer komplekse i forhold til trær, da det kan ha sykluser, sløyfer osv.
6. Grafen krysses av DFS : Dybde Første søk og i BFS : Bredde første søkealgoritme.
7. Grafen kan være syklisk eller syklisk.
8. Det er hovedsakelig to typer grafer: Direkte og ikke-dirigerte grafer.
9. Grafapplikasjoner: Farging av kart, en lgoritmer, graffarging, jobbplanlegging osv.
10. I graf, nr. av kantene avhenger av grafen.
11. Grafen er en nettverksmodell.

Trær

1. Treet er en spesiell grafform, dvs. minimalt tilkoblet graf og har bare en bane mellom to hjørner.
2. Treet er et spesielt tilfelle av graf uten sløyfer, ingen kretser og ingen selvløkker.
3. I treet er det nøyaktig en rot node og alle barn har bare en forelder.
4. I trær er det foreldrebarnsforhold slik at flyt kan være der med retning topp til bunn eller omvendt.
5. Trær er mindre komplekse enn grafer uten å ha sykluser, ingen selvløkker og fremdeles koblet sammen.
6. Traversering av tre er en slags spesiell tilfelle av traversal av grafen. Treet krysses i Forhåndsbestilling , In-Order og Etterbestilling (alle tre i DFS eller i BFS algoritme)
7. Trær kommer i kategorien DAG: Directed Acyclic Graphs er en slags rettet graf som ikke har noen sykluser.
8. Ulike typer trær er: Binært tre , Binært søketre, AVL-tre, dynger.
9. Treapplikasjoner : sortering og søking som Tree Traversal & Binary Search.
10. Treet har alltid n-1 kanter.
11. Tree er en hierarkisk modell.