Matematicas Discretas

INSTITUTO TECNOLOGICO DE CD. GUZMAN.

MATERIA: MATEMATICAS DISCRETAS


MAESTRA: SANDRA VAZQUEZ ROLON

ALUMNO: JUAN CARLOS PALENCIA MENDOZA

CARRERA: ING. EN INFORMATICA

TRABAJO: UNIDAD 6 GRAFOS

UNIDAD 6 (Teoría de grafos)


   Estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y unaselección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Estructura de lista * lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.1* * lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.Estructuras matriciales * Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V(vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado) * * Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de lo contrario, es 0.Operaciones en Grafos
Subdivisión elemental de unaarista se convierte en Se reemplaza la arista  por dos aristas   y un vértice w.Después de realizar esta operación, el grafo queda con un vértice y una arista más.
Eliminación débil de un vérticeSi  y g(v) = 2 (Sea v un vértice del grafo y de grado dos) eliminarlo débilmente significa reemplazarlo por una arista que une los vértices adyacentes a v. se convierte en Entonces e' y e'' desaparecen yaparece 6.1 Elementos y características de los grafos. |
Grafos simples
Un grafo es simple si a lo sumo sólo 1 arista une 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 Multigráfica o Gráfo múltiple.
 

Grafos conexos
Un grafo es conexo si cada par de vértices está conectado por uncamino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es fuertemente 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.
 
Grafos completos
Un grafo es completo si existen aristas uniendo todos lospares 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.
 
Grafos bipartitos
Un grafo G es bipartito si puede expresarse como G = {V_1 cup V_2, A} (es decir, sus vértices son launió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.
 Lazos o bucles
Un lazo o 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:
* Vneqemptyset
* Esubseteq {xinmathcal P(V): |x|=2} es un conjunto de pares no ordenados de elementos de V,.
Un par no ordenado es un conjunto de...