Grafos

UNIVERSIDAD AUTÓNOMA DE CAMPECHE

FACULTAD DE INGENIERÍA

INGENIERÍA EN SISTEMAS COMPUTACIONALES

Nombre del Alumno:

Noé del Carmen Avilez Cárdenas

Asignatura:

Estructura de Datos I

Docente:

Carlos Mario Sosa Silva

Grado y Grupo

4 “A”

Trabajo:

INVESTIGACIÓN

Fecha de entrega

20/Junio/2011

Contenido

GRAFOS 3

¿QUÉ ES UN GRAFO Y DE QUE CONSTA? 3

LAZOO BUCLE 3

Subgrafo 3

MATRIZ DE ADYACENCIA 4

Construcción de la matriz a partir de un grafo 5

Ejemplo de grafo no dirigido 5

Ejemplo de grafo dirigido 5

Propiedades de la matriz de adyacencia 6

CAMINO, CAMINO CERRADO Y CAMINO SIMPLE 6

CICLO 7

GRAFO CONEXO 7

ARBOL 8

Características y propiedades de los arboles 9

MULTIGRAFO 9

GRAFICAS 10GRAFICA COMPLETA 10

GRAFICA ETIQUETADA 11

BIBLIOGRAFIA 11

LINK DEL TRABAJO 11

GRAFOS

¿QUÉ ES UN GRAFO Y DE QUE CONSTA?

Un grafo es un objeto matemático definido por:

• Un conjunto finito de elementos llamados vértices

• Un conjunto finito de elementos llamados aristas

• Una aplicación, llamada incidencia, que a cada arista hace corresponder un conjunto(noordenado) formado por uno o dos vértices, llamados sus extremos

Según esta definición de grafo, puede existir un número ilimitado de aristas a las que correspondan un mismo par de vértices, son las llamadas aristas multiples.

LAZO O BUCLE

Arista que conecta a un nodo consigo mismo a=(u,u); son aristas a las que corresponda un único vértice, son las llamadas lazo.

Subgrafo

Subgrafo de ungrafo G es un grafo cuyos conjuntos de aristas y vértices son subconjuntos de los de G. Como aplicación de incidencia, la inducida por la de G.

Subgrafo inducido por un cierto subconjunto de vértices V es aquel subgrafo cuyo conjunto de vértices es este V y cuyo conjunto de aristas es el mayor posible, es decir, el subconjunto de aristas formado por todas aquellas cuyos extremos están ambos en elsubconjunto V.

MATRIZ DE ADYACENCIA

La adyacencia es la relación existente entre dos vértices cuando a alguna arista le corresponde el conjunto formado por ellos dos. En términos gráficos, la adyacencia es la relación que una arista genera entre sus extremos.

La matriz de adyacencias es una matriz cuadrada donde para i≠j, el elemento aij es el numero de aristas cuyos extremos son losvértices vi y vj; aij es dos veces el numero de lazos con extremo vi. Intuitivamente, para todo i, j, aij indica de cuantas maneras se puede ir del vértice vi al vértice vj siguiendo una arista.

La matriz de adyacencias de todo grafo es simétrica. Como cada lazo supone dos maneras de ir desde el vértice hasta sí mismo, entonces todas las aristas, lazos o no lazos, son contadas dos veces en lamatriz de adyacencias: una por cada sentido en que pueden recorrerse.

Dado un grafo, no tiene una única matriz de adyacencias, sino que cada ordenación de los vértices da lugar a una (posiblemente) distinta. Para los siguientes grafo y subgrafo

|0 |2 |0 |1 |
|2 |0 |2 |1 |
|0 |2 |0 |1 |
|1 |1 |1 |2 |
|0 |1|0 |0 |
|1 |0 |1 |1 |
| 0 |1 |0 |1 |
|0 |1 |0 |2 |

Las matrices quedan:

Construcción de la matriz a partir de un grafo

➢ Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.
➢ Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicacióncorrespondiente de la matriz.
➢ Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 2 en vez de 1.
➢ Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos (elementos).
Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa.
Ejemplo de grafo no dirigido...