Hvad er en komplet graf?

Bedste svar

Er du bekendt med strukturen i et molekyle af cyclopropan? En cyclopropan er et alicyklisk carbonhydrid, der består af tre carbonatomer arrangeret i en ringstruktur som denne

Observer strukturen nøje. Ignorer brintatomer for nu og bemærk bare de kovalente bindinger mellem et hvilket som helst to carbonatom. Vær opmærksom på, at hvert kulstofatom er bundet til hvert andet kulstofatom i et cyclopropanmolekyle. Dette er den grundlæggende intuition bag en komplet graf.

Nu en formel definition:

En komplet graf, der består af n hjørner, er en tilsluttet graf, således at der findes en sti med længde en mellem de to hjørner i grafen . Med andre ord, i en komplet graf, er hver toppunkt ved siden af ​​de resterende hjørner, således at antallet af kanter i grafen er nøjagtigt \, \ binom {n} {2}

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

Bemærk, at i ovenstående graf er hvert toppunkt knyttet til alle andre hjørner. Derfor er det en komplet graf.

Svar

Forskel mellem graf og treddatastruktur:

Graf

1. I graf der kan være mere end en sti, dvs. grafen kan have envejs eller tovejs stier mellem noder.
2. I grafen findes der ikke et sådant begreb rod knude.
3. Graf kan have sløjfer, kredsløb såvel som kan have selvsløjfer.
4. I graf er der ikke et sådant forældrebarnsforhold.
5. Grafer er mere komplekse sammenlignet med træer, da det kan have cyklusser, sløjfer osv.
6. Grafen krydses af DFS : Dybde Første søgning og i BFS : Algoritme for første søgning i bredde.
7. Grafen kan være cyklisk eller cyklisk.
8. Der er hovedsageligt to typer grafer: Direkte og ikke-dirigerede grafer.
9. Grafapplikationer: Farvning af kort, en lgoritmer, graffarvning, jobplanlægning osv.
10. I graf, nr. af kanter afhænger af grafen.
11. Graf er en netværksmodel.

Træer

1. Træ er en speciel form for graf, dvs. minimalt forbundet graf og har kun en sti mellem to to hjørner.
2. Træ er et specielt tilfælde af graf uden sløjfer, ingen kredsløb og ingen selvløkker.
3. I træet er der nøjagtigt en rod node og hvert barn har kun en forælder.
4. I træer er der et forældrebarnsforhold, så flow kan være der med retning top til bund eller omvendt.
5. Træer er mindre komplekse end grafer som ingen cyklusser, ingen selvløkker og stadig forbundet.
6. Traversering af træ er en slags specielt tilfælde af traversal af grafen. Træ krydses i Forudbestilling , In-Order og Efterbestilling (alle tre i DFS eller i BFS algoritme)
7. Træer kommer i kategorien DAG: Directed Acyclic Graphs er en slags rettet graf, der ikke har nogen cyklusser.
8. Forskellige typer træer er: Binært træ , Binært søgetræ, AVL-træ, dynger.
9. Træapplikationer : sortering og søgning som Tree Traversal & Binary Search.
10. Træ har altid n-1 kanter.
11. Tree er en hierarkisk model.