Definición de grafos

Definición de grafos

Un grafo G es un par ordenado G= (V, E), donde:

• V es un conjunto de vértices o nodos, y

• E es un conjunto de aristas o arcos, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.

Se llama orden del grafo G a su número de vértices, |V|.

El grado de un vértice o nodo v \in V es igual al número de arcos que lo tienen como extremo.

Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V, E) donde:

Es un conjunto de pares no ordenados de elementos de V.

Un par no ordenado es un conjunto de la forma {a, b}, de manera que {a, b}= {b, a}. Para los grafos, estos conjuntos pertenecen al conjunto potencia de V, denotado P (V), y son de cardinalidad 2.

Grafo dirigido

Un grafo dirigido o dígrafo es un grafo G = (V, E) donde:

Es un conjunto de pares ordenados de elementos de V.

Dada una arista (a, b), a es su nodo inicial y b su nodo final.

Por definición, los grafos dirigidos no contienen bucles.

Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.

Caracterización de un grafo

Grafos simples

Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina multígrafo.

Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Grafos completos

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente , siendo el grafo completo de n vértices.

Un , es decir, grafo completo de n vértices tiene exactamente aristas.

La representación gráfica de los como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos

Un grafo G es bipartito si puede expresarse como (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

• y son disjuntos y no vacíos.

• Cada arista de A une un vértice de con uno de .

• No existen aristas uniendo dos elementos

...