matematicas discretas u6









Matemáticas Discretas



Actividad de la unidad 6



Catedrático:

Lic. Isidro Hernández Castellanos



Alumno:

Jorge Luis Guzmán Rodríguez



1er Semestre Grupo “A” Ing. Informática

Turno Matutino





Teapa, Tabasco a 10 de Diciembre de 2012
6.1. Elementos y características de los grafos.

Definición: Un grafo G= (N, A) consta de un conjunto de nodos N y un conjunto de aristas A, en donde a cada arista es un par no ordenado de nodos (vértices o puntos). Una arista en general se representa por {a, b}. A las aristas también se le llaman segmentos. Una forma de representar grafos es mediante círculos para los nodos, conectados por líneas para las aristas.

Ejemplo 1:

El Grafo G que consta de los nodosN y segmentos S
Se denota como: G(N, S) donde:

N= {n1, n2, n3, n4, n5, n6, n7, n8}
A= {{n1, n2}, {n1, n5}, {n3, n4}, {n4, n7}, {n2, n6}, {n6, n2}}

6.1.1. Componentes de un grafo (vértices, aristas, lazos, valencia)

Vértice de un grafo:
Un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de vértices y unconjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una redsemántica es un grafo en donde los vértices representan conceptos o clases de objetos.

Los dos vértices que conforman una arista se llaman puntos finales ("endpoints", en inglés), y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v, w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todoslos vértices adyacentes a v.

Aristas de un grafo:
Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.
Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.

Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

Aristas Adyacentes: Se dice que dos aristas sonadyacentes si convergen en el mismo vértice.
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
Cruce: Son dos aristas que cruzan en un punto

Lazos de un grafo:
Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodofinal coinciden. Es aquella arista que sale de un vértice y regresa al mismo vértice.







Valencia de un vértice:
Es el número de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:
Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3
Hay que observar como en el caso del vértice del lazo solo se considera una vez, entrada o salidapero no ambos.

6.1.2. Tipos de grafos (simples, completos, bipartidos, planos, conexos, ponderados).

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 Grafo múltiple.

Grafos completos
Un grafoes 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.



Grafo bipartido
Es el grafo que está compuesta por dos...