Matemáticas | Conceptos básicos de la teoría de grafos – Conjunto 1

Un gráfico es una estructura de datos que está definida por dos componentes:

1. Un Node o un vértice.
2. Una arista E o par ordenado es una conexión entre dos Nodes u,v que se identifica por un par único (u,v). El par (u,v) está ordenado porque (u,v) no es lo mismo que (v,u) en el caso de un gráfico dirigido. El borde puede tener un peso o se establece en uno en el caso de un gráfico no ponderado.

Considere el siguiente gráfico,

Para saber sobre “Representación gráfica” haga clic aquí

Aplicaciones:
Graph es una estructura de datos que se usa ampliamente en nuestra vida real.

1. Red social: cada usuario se representa como un Node y todas sus actividades, sugerencias y lista de amigos se representan como un borde entre los Nodes.
2. Google Maps: varias ubicaciones se representan como vértices o Nodes y las carreteras se representan como bordes y la teoría de grafos se usa para encontrar el camino más corto entre dos Nodes.
3. Recomendaciones en sitios web de comercio electrónico: la sección «Recomendaciones para usted» en varios sitios web de comercio electrónico utiliza la teoría de gráficos para recomendar elementos de tipo similar a la elección del usuario.
4. La teoría de grafos también se usa para estudiar moléculas en química y física.

Más sobre gráficos:
Características de los gráficos:

1. Node adyacente: Se dice que un Node ‘v’ es un Node adyacente del Node ‘u’ si y solo si existe un borde entre ‘u’ y ‘v’.
2. Grado de un Node: en un gráfico no dirigido, el número de Nodes que inciden en un Node es el grado del Node.
   En el caso del grafo dirigido, el Ingrado del Node es el número de aristas que llegan a un Node.
   El grado de salida del Node es el número de aristas que salen de un Node.

   

   

3. Ruta: una ruta de longitud ‘n’ desde el Node ‘u’ hasta el Node ‘v’ se define como una secuencia de n+1 Nodes.
   P(u,v)=(v0,v1,v2,v3…….vn)

   Una ruta es simple si todos los Nodes son distintos, la excepción es que el origen y el destino son los mismos.

4. Node aislado: un Node con grado 0 se conoce como Node aislado. El Node aislado se puede encontrar mediante la búsqueda primero en amplitud (BFS). Encuentra su aplicación en la red LAN para encontrar si un sistema está conectado o no.
   
   

Tipos de gráficos:

1. Gráfico dirigido:
   un gráfico en el que la dirección del borde se define en un Node particular es un gráfico dirigido.
   • Gráfico acíclico dirigido: es un gráfico dirigido sin ciclo. Para un vértice ‘v’ en DAG no hay un borde dirigido que comience y termine con el vértice ‘v’.
     a) Aplicación: análisis crítico del juego, evaluación del árbol de expresión, evaluación del juego.
   • Árbol: un árbol es solo una forma restringida de gráfico. Es decir, es un DAG con la restricción de que un niño solo puede tener un padre.
2. Gráfico no dirigido:
   un gráfico en el que la dirección del borde no está definida. Entonces, si existe un borde entre el Node ‘u’ y ‘v’, entonces hay un camino desde el Node ‘u’ al ‘v’ y viceversa.
   • Grafo conexo: Un grafo es conexo cuando hay un camino entre cada par de vértices. En un grafo conexo no hay ningún Node inalcanzable.
   • Gráfico completo: un gráfico en el que cada par de vértices del gráfico está conectado por una arista. En otras palabras, cada Node ‘u’ es adyacente a todos los demás Nodes ‘v’ en el gráfico ‘G’. Un gráfico completo tendría n(n -1)/2 aristas. Ver abajo para la prueba.
   • Gráfico biconexo: un gráfico conexo que no se puede dividir en más partes mediante la eliminación de cualquier vértice. Es un gráfico sin punto de articulación.
     

     
     

Prueba para el gráfico completo:

1. Considere un gráfico completo con n Nodes. Cada Node está conectado a otros n-1 Nodes. Así se convierte en n * (n-1) aristas. Pero esto cuenta cada borde dos veces porque este es un gráfico no dirigido, así que divídalo por 2.
2. Por lo tanto, se convierte en n(n-1)/2.

Considere el gráfico dado,
//Omita los bordes repetitivos
Bordes en el Node A = (A,B),(A,C),(A,E),(A,C).
Aristas en el Node B = (B,C),(B,D),(B,E).
Aristas en el Node C = (C,D),(C,E).
Aristas en el Node D = (D,E).
Aristas en el Node E = VACÍO.https://en.wikipedia.org/wiki/Graph_theory Aristas
totales = 4+3+2+1+0=10 aristas.
Número de Nodes = 5.
Así n(n-1)/2=10 aristas.
Así probado.

Lea el siguiente conjunto: conceptos básicos de teoría de grafos