Elementos, características y componentes de los grafos y tipos de grafos

Elementos, características y componentes de los grafos y tipos de grafos.

What are the graph?

A graph is a mathematical structure used to model relationships between objects. It consists of a set of nodes (also called vertices) and a set of edges (or connections) that join pairs of nodes together. Graphs can be directed (when the edges have a direction) or undirected (when they have no direction). They are used in many areas, such as computer science, mathematics, biology, and social sciences.

Elementos de los grafos

1. Nodos o vértices (Vértices)

Representan los puntos o entidades dentro del grafo.

Se identifican de forma única(por medio de etiquetas por ejemplo).

Ejemplo: Ciudades en un mapa, personas en una red social.

2. Aristas o enlaces

Representan las conexiones entre nodos.

Pueden tener diferentes características:

Dirigido: Con flechas que indican una relación unidireccional.

No dirigido: Relación bidireccional entre dos nodos.

Ponderado: asociado a un valor o peso (como la distancia o el coste).

3. Grado de un nodo (Grado)

Es el número de aristas conectadas a un nodo.

En grafos dirigidos:

En grado: número de aristas que llegan al nodo.

Grado de salida: Número de aristas que salen del nodo.

4. Caminos

Secuencia de nodos conectados por aristas.

Puede ser simple (sin repetir nodos) o formar un ciclo (cuando vuelve al nodo inicial).

5. Subgrafos

Partes de un grafo que constan de un subconjunto de sus nodos y aristas.

Característica

1.Componentes básicos:

Nodos o vértices: Puntos que representan entidades o elementos.

Bordes o Aristas: Conexiones entre nodos que indican relaciones.

2. Naturaleza de los bordes:

Dirigido: Las conexiones tienen una dirección específica.

No dirigido: Las conexiones no tienen una dirección; La relación es bidireccional.

3. Conectividad: 

Grafo conexo: Hay una ruta entre cualquier par de nodos. 

Grafo desconectado: Algunos nodos no están conectados entre sí.

4. Pesos de los bordes

Ponderado: cada borde tiene un valor asociado, como la distancia, el coste o el tiempo. Sin ponderar: las aristas no tienen valores asignados.

5. Ciclos: 

Grafo acíclico: No contiene ciclos (rutas cerradas). 

Gráfico cíclico: Contiene al menos un ciclo.

6. Grado de nodos: 

Grado: Es el número de aristas incidentes en un nodo. 

Grado de entrada: En grafos dirigidos, las aristas que llegan al nodo.

 Grado de salida: En grafos dirigidos, las aristas que salen del nodo.

7. Simetría:

Grafo simétrico: En un grafo dirigido, si para cada arista (u,v)(u, v)(u,v)

existe la arista inversa (v,u)(v, u)(v,u).

Gráfico asimétrico: No cumple con la propiedad anterior.

8. Conjunto de nudos y aristas:

Orden del gráfico: Número total de nodos.

Tamaño del gráfico: Número total de aristas.

9. Tipos especiales de gráficos: 

Gráfico completo: Todos los nodos están conectados entre sí. 

Grafo bipartito: Los nodos se dividen en dos conjuntos disjuntos y las aristas solo conectan nodos de diferentes conjuntos.

             COMPONENTES DE LOS GRAFOS                                               

Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos. Estas a su vez pueden ser: Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice. Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo. Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo. Cruce: Son dos aristas que cruzan en un punto.

Vértices: Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado. Estos a su vez pueden ser: Vértices Adyacentes: Si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

 Vértice Aislado: Es un vértice de grado cero. 

Vértice Terminal: Es un vértice de grado 1.

ARISTAS

Aristas Adyacentes

Concepto de Aristas Adyacentes En un grafo, que es una estructura matemática utilizada para modelar relaciones entre pares de objetos, una arista (o arco) conecta dos nodos (o vértices). Las aristas adyacentes son aquellas que comparten un vértice común. Por ejemplo, en un grafo GG si tenemos los vértices V1,V2, V3 y aristas AA que conectan estos vértices, podemos decir que las aristas a1 y a2 son adyacentes si hay un vértice que ambos comparten.

Aristas Paralelas 

aristas Paralelas en grafos Las aristas paralelas en un grafo son aquellas que conectan los mismos dos vértices. En otras palabras, son múltiples aristas que tienen los mismos puntos de inicio y fin. Estas aristas se encuentran comúnmente en grafos multigrafos, donde se permite que existan múltiples aristas entre un par de vértices. Ejemplo Considera un grafo con los vértices A y B, y dos aristas a1 y a2 que conectan A y B:

A---------a1--------->B 

A--------a2--------->B

Aristas Cíclicas 

Aristas Cíclicas en grafos Las aristas cíclicas en grafos están relacionadas con los ciclos. Un ciclo en un grafo es una secuencia de aristas que comienza y termina en el mismo vértice, pasando por un conjunto de vértices y aristas sin repetir ninguno, excepto el vértice inicial y final. Las aristas que forman parte de un ciclo son consideradas aristas cíclicas. Ejemplo Considera un grafo con los vértices A, B, C y D, y las siguientes aristas: (A,B) (B,C) (C,D) (D,A)

Cruce 

El cruce en grafos se refiere a un fenómeno que ocurre cuando dos aristas de un grafo se intersecan en un plano de manera no deseada. En otras palabras, es el punto donde dos aristas se cruzan en un diagrama bidimensional del grafo. Los cruces en un grafo pueden complicar la interpretación visual de la estructura del grafo, y a menudo se busca minimizarlos en los diagramas. Ejemplo Considera un grafo con vértices A, B, C y D, y las aristas (A,C) y (B,D) que se cruzan: 

A----C

\ / 

\/

 /\ 

/ \ 

B----D

VERTICES

Vértices Adyacentes, En la teoría de grafos, vértices adyacentes son aquellos que están conectados directamente por una arista. En otras palabras, dos vértices son adyacentes si hay una arista que los une. Ejemplo Supongamos que tenemos un grafo con los vértices A, B, C y D y las siguientes aristas:

(A,B) (A,C) (B,D)

 En este grafo:

Los vértices A y B son adyacentes porque están conectados por la arista (A,B).

Los vértices A y C son adyacentes porque están conectados por la arista (A,C).

Los vértices B y D son adyacentes porque están conectados por la arista (B,D).

Vértice Aislado 

En la teoría de grafos, un vértice aislado es un vértice que no está conectado a ningún otro vértice del grafo mediante una arista. En otras palabras, un vértice aislado no tiene aristas incidentes. 

Ejemplo: Considera un grafo con los vértices A, B, C, D y E, y las siguientes aristas:

(A,B) 

(B,C) 

Ejemplo:    A-----B-----C 

                      D          E

En este grafo: Los vértices A, B y C están conectados por aristas. Los vértices D y E no tienen ninguna arista que los conecte a otros vértices. En este caso, D y E son vértices aislados porque no tienen ninguna arista incidente.

Vértice Terminal 

Un vértice terminal es un vértice que tiene exactamente una arista incidente, es decir, está conectado a otro vértice por solo una arista. Este tipo de vértice también se conoce como vértice de grado 1. Ejemplo Considera un grafo con los vértices A, B, C y D, y las siguientes aristas: 

(A,B)

 (A,C) 

(A,D) 

En este grafo, los vértices B, C y D son vértices terminales porque cada uno de ellos está conectado al vértice AA por una única arista.                    

 B

 | 

A---C 

 |

  D

TIPOS DE GRAFOS

 Grafos no dirigidos: Un grafo no dirigido es un tipo de grafo en el que las aristas no tienen un sentido definido y representan relaciones simétricas. Esto significa que una arista puede recorrerse en cualquier dirección y desde cualquiera de sus puntos. En un grafo no dirigido, las aristas se representan como pares no ordenados {u,v}, donde u y v son los extremos de la arista. Un ejemplo de grafo no dirigido es una red de amistad en las redes sociales, ya que si eres amigo de alguien, él también es amigo tuyo. Los grafos no dirigidos no pueden tener aristas paralelas o bucles propios, ya que serían redundantes.

Dígrafo o Grafos dirigidos: 

Los grafos dirigidos, también conocidos como dígrafos, son estructuras que consisten en un conjunto de vértices y aristas, donde cada arista tiene un sentido definido y se representa con una flecha Los grafos dirigidos se diferencian de los grafos no dirigidos, en los que las aristas son relaciones simétricas y no apuntan en ningún sentido. Los grafos dirigidos acíclicos (DAGs) son grafos dirigidos que no contienen ciclos. Son útiles en problemas de programación y planificación, ya que permiten representar dependencias sin ciclos. Un grafo dirigido se denomina fuertemente conexo si existe un camino desde cualquier vértice a cualquier otro vértice.

Grafos etiquetados: 

En teoría de grafos, un grafo etiquetado es un grafo cuyos vértices tienen nombres o etiquetas. Estas etiquetas comúnmente son números enteros. En ocasiones, también se habla de grafo de aristas etiquetadas, de modo que son las aristas las que tienen etiquetas, y de este modo se distingue de un grafo de vértices etiquetados.

Grafos completos:

 Un grafo completo es un grafo en el que todos los pares de vértices están conectados por una arista. En otras palabras, un grafo completo contiene todas las aristas posibles. Los grafos completos son un tipo de grafo simple, al igual que los grafos dirigidos. Los grafos dirigidos tienen aristas que conectan los nodos con una direccionalidad clara.

Grafos conexos 

Un grafo conexo es un grafo en el que todos sus vértices están conectados por un camino. En otras palabras, para cualquier par de vértices, existe al menos un camino que los une. En un grafo no dirigido, los vértices adyacentes están conectados por un camino de longitud 1, los segundos vecinos por un camino de longitud 2, y así sucesivamente. Un grafo que no es conexo se llama grafo disconexo o inconexo. Un grafo con múltiples componentes es no conexo. En teoría de grafos, también se pueden definir otros tipos de conectividad, como: Débilmente conexo, Unilateralmente conexo, Fuertemente conexo, Recursivamente conexo. 

Árbol: 

En teoría de grafos, un grafo árbol es un grafo no dirigido y acíclico conexo, en el que dos vértices están conectados por un único camino. Su forma recuerda a un árbol, de ahí su nombre. En informática, un árbol es un tipo abstracto de datos (TAD) que imita la estructura jerárquica de un árbol. Está representado como un conjunto de nodos enlazados, con un valor en la raíz y subárboles con un nodo padre. 

Bosque:

En teoría de grafos, un bosque es un grafo no dirigido en el que dos vértices cualesquiera están conectados por un máximo de un camino. También se puede definir como un grafo acíclico no dirigido o como una unión disjunta de árboles. Las componentes conexas de un bosque son árboles. Un árbol es un bosque conexo, es decir, un grafo que se ramifica y no forma ciclos. Los árboles son óptimos para conexidad y aciclicidad. Los árboles tienen muchas aplicaciones, especialmente en almacenamiento y recuperación de datos, búsqueda y comunicaciones.

CITAS BIBLIOGRAFICAS

Leonhard Euler (1707-1783) Considerado el padre de la teoría de grafos, Euler introdujo el concepto en 1736 al resolver el problema de los Siete Puentes de Königsberg, un caso clásico en teoría de grafos. Su trabajo sentó las bases de la teoría de grafos como disciplina matemática. 

Douglas B. West Autor del libro "Introduction to Graph Theory " , una obra fundamental que cubre los aspectos teóricos y aplicados de los grafos. Este libro es ampliamente usado en cursos universitarios y como referencia en investigación.

 Reinhard Diestel Autor de "Graph Theory " , un libro que abarca teoría avanzada de grafos con un enfoque en matemática pura. Es reconocido por su enfoque claro y la conexión entre conceptos teóricos y aplicaciones.