¿Qué es un gráfico completo?

Mejor respuesta

¿Está familiarizado con la estructura de una molécula de ciclopropano? Un ciclopropano es un hidrocarburo alicíclico que consta de tres átomos de carbono dispuestos en una estructura anular como esta

aña

aña Observa cuidadosamente la estructura. Ignore los átomos de hidrógeno por ahora y observe los enlaces covalentes entre dos átomos de carbono. Observe que cada átomo de carbono está enlazado con todos los demás átomos de carbono en una molécula de ciclopropano. Esta es la intuición básica detrás de un gráfico completo.

Ahora una definición formal:

Un gráfico completo que consta de n vértices es un gráfico conectado de manera que existe una ruta de longitud uno entre dos vértices cualesquiera del gráfico . En otras palabras, en un gráfico completo, cada vértice es adyacente a los vértices restantes, de modo que el número de aristas en el gráfico es exactamente \, \ binom {n} {2}

A Un mejor ejemplo de un gráfico completo es \, K\_5 \,

Observe que en el gráfico anterior, cada vértice está unido a todos los demás vértices. Por lo tanto, es un gráfico completo.

Respuesta

Diferencia entre el gráfico y la estructura de datos de árbol:

Gráfico

1. En gráfico puede haber más de una ruta, es decir, el gráfico puede tener rutas unidireccionales o bidireccionales entre nodos.
2. En el gráfico no existe tal concepto de nodo raíz .
3. Graph puede tener bucles, circuitos y también puede tener bucles propios.
4. En Graph no existe tal relación padre-hijo.
5. Los gráficos son más complejos en comparación con los árboles, ya que pueden tener ciclos, bucles, etc.
6. El gráfico está atravesado por DFS : profundidad Primera búsqueda y en BFS : algoritmo de búsqueda primero de amplitud.
7. El gráfico puede ser cíclico o acíclico.
8. Hay principalmente dos tipos de gráficos: gráficos dirigidos y no dirigidos.
9. Aplicaciones de gráficos: coloración de mapas, una algoritmos, coloración de gráficos, programación de trabajos, etc.
10. En Graph, no. de los bordes dependen del gráfico.
11. El gráfico es un modelo de red.

Árboles

1. El árbol es una forma especial de gráfico, es decir, un gráfico mínimamente conectado y que tiene solo una ruta entre dos vértices cualesquiera.
2. El árbol es un caso especial de gráfico que no tiene bucles, circuitos ni auto-bucles.
3. En el árbol hay exactamente una raíz nodo y cada hijo tiene solo un padre.
4. En los árboles, existe una relación padre / hijo, por lo que el flujo puede estar allí con dirección de arriba a abajo o viceversa.
5. Los árboles son menos complejos que los gráficos, ya que no tienen ciclos, ni ciclos automáticos y aún están conectados.
6. El recorrido del árbol es una especie de caso especial de recorrido de gráfico. El árbol se atraviesa en Pedido por adelantado , En pedido y Posterior al pedido (los tres en DFS o en BFS algoritmo)
7. Los árboles pertenecen a la categoría de DAG: Los gráficos acíclicos dirigidos son un tipo de gráfico dirigido que no tiene ciclos.
8. Los diferentes tipos de árboles son: Binary Tree , Binary Search Tree, AVL tree, Heaps.
9. Aplicaciones de árbol : ordenando y buscando como Tree Traversal y Binary Search.
10. El árbol siempre tiene n-1 bordes.
11. Árbol es un modelo jerárquico.