Gráfico conectado

Un gráfico conexo  es un gráfico que contiene exactamente un componente conexo . Esto significa que hay al menos un camino entre cualquier par de vértices en este gráfico .

Ejemplos de aplicación

Una aplicación directa de la teoría de grafos es la teoría de redes, y su aplicación es la teoría de redes electrónicas. Por ejemplo, todas las computadoras conectadas a Internet forman un gráfico conectado, y aunque es posible que un par de computadoras separadas no estén conectadas directamente (en la formulación de gráficos, no deben estar conectadas por un borde), la información puede transmitirse desde cada computadora a cualquier otra. otro (hay un camino desde cualquier vértice del grafo a cualquier otro).

Conectividad para grafos dirigidos

En grafos dirigidos se distinguen varios conceptos de conectividad.

Se dice que un grafo dirigido es fuertemente conexo si tiene un camino (dirigido) desde cualquier vértice a cualquier otro o, de manera equivalente, el grafo contiene exactamente un componente fuertemente conexo .

Un grafo dirigido se llama débilmente conexo si es un grafo no dirigido conexo obtenido a partir de él reemplazando aristas dirigidas por no dirigidas.

Algunos criterios de conectividad

Aquí hay algunas definiciones de criterio (equivalentes) de un grafo conexo:
Un grafo se llama simplemente conexo (conectado) si:

  1. Tiene un componente conectado.
  2. Hay un camino desde cualquier vértice a cualquier otro vértice
  3. Hay un camino desde un vértice dado a cualquier otro vértice
  4. Contiene un subgrafo conectado que incluye todos los vértices del grafo original
  5. Contiene como subgrafo un árbol que incluye todos los vértices del grafo original (tal árbol se llama árbol de expansión )
  6. Cuando sus vértices se dividen arbitrariamente en 2 grupos, siempre hay al menos 1 arista que conecta un par de vértices de diferentes grupos

Véase también