Cel mai bun răspuns
Cunoașteți structura unei molecule de ciclopropan? Un ciclopropan este o hidrocarbură aliciclică formată din trei atomi de carbon dispuși într-o structură inelată ca aceasta
Observați cu atenție structura. Ignorați atomii de hidrogen pentru moment și observați doar legăturile covalente dintre oricare doi atomi de carbon. Observați că fiecare atom de carbon este legat cu orice alt atom de carbon dintr-o moleculă de ciclopropan. Aceasta este intuiția de bază din spatele unui grafic complet .
Acum o definiție formală:
Un grafic complet format din n vârfuri este un grafic conectat astfel încât să existe o cale de lungime una între oricare două vârfuri ale graficului . Cu alte cuvinte, într-un grafic complet, fiecare vârf este adiacent vârfurilor rămase, astfel încât numărul muchiilor din grafic să fie exact \, \ binom {n} {2}
A un exemplu mai bun de grafic complet este \, K\_5 \,
Observați că în graficul de mai sus, fiecare vârf este unit toate celelalte vârfuri. Prin urmare, este un grafic complet.
Răspuns
Diferența dintre grafic și structura de date arborescentă:
Grafic
- În grafic poate exista mai multe căi, adică graficul poate avea căi unidirecționale sau bidirecționale între noduri.
- În grafic nu există un astfel de concept de nodul rădăcină .
- Graficul poate avea bucle, circuite și poate avea autocircule.
- În Grafic nu există o astfel de relație părinte copil.
- Graficele sunt mai complexe în comparație cu arborii, deoarece pot avea cicluri, bucle etc.
- Graficul este parcurs de DFS : Adâncime Prima căutare și în BFS : algoritm Breadth First Search.
- Graficul poate fi ciclic sau aciclic.
- Există în principal două tipuri de grafice: grafice direcționate și nedirecționate.
- Aplicații grafice: colorarea hărților, a lgoritmi, colorarea graficelor, programarea lucrărilor etc.
- În grafic, nr. de margini depinde de grafic.
- Graficul este un model de rețea.
Copaci
- Arborele este o formă specială de grafic, adică un grafic minim conectat și având o singură cale între oricare două vârfuri.
- Arborele este un caz special de grafic fără bucle, fără circuite și fără autocircuituri.
- În arbore există exact o rădăcină / span> nod și fiecare copil are un singur părinte.
- În copaci, există relația copil părinte, astfel încât fluxul poate fi acolo cu direcția de sus în jos sau invers.
- Arborii sunt mai puțin complecși decât graficii, deoarece nu au cicluri, nu au bucle de sine și sunt încă conectați.
- Traversarea arborelui este un fel de caz special de traversare de grafic. Arborele este parcurs în precomandă , în ordine și Post-comandă (toate trei în DFS sau în BFS algoritm)
- Arborii aparțin categoriei DAG: Graficele aciclice direcționate este un fel de grafic direcționat care nu are cicluri.
- Diferite tipuri de arbori sunt: Arborele binar , Arborele de căutare binar, arborele AVL, grămezi.
- : sortare și căutare, cum ar fi Căutare transversală și binară a arborelui.
- Arborele are întotdeauna n-1 margini.
- Arborele este un model ierarhic.