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

INSTITUTO TECNOLÓGICO SUPERIOR DE JEREZ

1er Semestre

 Ingeniería en Sistemas Computacionales

MATEMÁTICAS DISCRETAS

“TEMA V. TEORÍA DE GRAFOS”

Docente: I.S.C. Ricardo Saldivar Quezada

Alumna: Pritschella Berenice Flores Estrada

Jerez De García Salinas, Zac.

Tema V. Teoría de grafos

5.1 Elementos, características y componentes de los grafos

Una gráfica (o gráfica no dirigida) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas(o arcos) tal que cada arista e ∈ E se asocia con un par no ordenado de vértices. Si existe una arista única e asociada con los vértices u y w, se escribe e = (v, w) o e = (w, v). En este contexto, (v, w) denota una arista entre v y w en una gráfica no dirigida y noes un par ordenado.

Una gráfica dirigida (o digráfica) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tales que cada arista e ∈ E está asociada con un par ordenado de vértices. Si hay una arista única e asociada con el par ordenado (v, w) de vértices, se escribe e = (v, w), que denota una arista de v a w.

5.1.1 Tipos de grafos

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 multigrafo.

Grafo completo.- 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 K, siendo Kn el grafo completo de n vértices.

Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2 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 G = {V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

·V1 y V2 son disjuntos y no vacíos.

·Cada arista de A une un vértice de V1 con uno de V2.

·No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

 

Grafos Planos.- Un grafo G es planar si admite una representación en el plano de tal forma que las aristas no se cortan, salvo en sus extremos. A dicha representación se le denomina grafo plano.

Se dice que un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte. A ese dibujo se le llama representación plana del grafo.

  

Grafo conexo.- Un grafo se dice que es conexo si cada par de sus vértices están conectados.

Es decir, G es conexo ⇐⇒ ∀u, v: ∃μ = [u, v]

En caso contrario, diremos que G es un grafo desconexo.

 

Grafos ponderados.- Llamamos grafos ponderados a los grafos en los que se asigna un número a cada una de las aristas. Este número representa un peso para el recorrido a través de la arista.

Este peso podrá indicar, por ejemplo, la distancia, el costo monetario o el tiempo invertido, entre otros.

Definimos la longitud de un camino en un grafo ponderado como la suma de los pesos de las aristas de ese camino.

Referencias:

Johnsonbaugh, R. (2005). Matemáticas discretas. En R. Johnsonbaugh, Matemáticas discretas (pág.320). Mexico: Pearson.

http://itpn.mx/recursosisc/1semestre/matematicasdiscretas/Unidad%20VI.pdf