Grafos, casanova rodriguez cecilia

UNIVERSIDAD AUTONOMA DE CAMPECHE

FACULTAD DE INGENIERIA

ISC

INVESTIGACIÓN

CASANOVA RODRIGUEZ CECILIA DEL CARMEN

20 DE JUNIO DE 2011

INDICE

DEFINICION DE GRAFOS………………………………………………………………3
DE QUE CONSTA UN GRAFO…………………………………………………………4
TIPOS DE GRAFOS……………………………………………………………………..4
* DIRIGIDOS
* NO DIRIGIDOS
TIPOS ESPECIALES DE GRAFOS……………………………………………………6
* Regular* Ciclo
* Completo
* Rueda
* Cubo
* Bipartito
* Bipartito completo
* Multígrafo
* Pseudografo
* Grafo conexo

CAMINNO………………………………………………………………………………..10
CICLO…………………………………………………………………………………….11
REPRESENTACION…………………………………………………………………....12
ARBOL……………………………………………………………………………………16
BIBLIOGRAFIA…………………………………………………………………………..17

DEFINICION

Los grafos sonestructuras discretas que aparecen ubicuamente en cada disciplina donde se requiera modelar algo. Por ejemplo, sirven para representar:
◮ El esquema organizacional de una empresa;
◮ Una red de computadores;
◮ Un árbol genealógico;
◮ La interacción entre científicos;
◮ La web semántica, etc.
En general, los grafos son mapas conceptuales que nos ayudan a representar nuestro conocimiento.

PUngrafo G está conformado por un conjunto no vacío V de vértices o nodos, y un conjunto E de arcos o aristas, tal que cada e ∈ E tiene un par (v1, v2) ∈ V × V asociado. En tal caso, decimos que ‘e’ conecta v1 con v2. Note que dos arcos diferentes pueden conectar al mismo par de vértices. En la anterior definición V y E pueden ser finitos o infinitos.

Ejemplo: Para representar una red decomputadores, podemos usar un grafo en que cada nodo es un servidor y cada arco es una conexión.

¿DE QUE CONSTA UN GRAFO?

Un grafo consta de dos cosas:
a) Un conjunto N cuyos elementos se llaman nodos, vértices o puntos.
b) Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos o aristas.
Denotamos un grafo por G(N, S) cuando queremos destacar las dos partes de G.
Losnodos u y v se llaman adyacentes si hay un segmento {u, v}.
Representamos de una manera natural los grafos por diagramas en el plano. O sea, cada nodo u de N se representa por un punto (o pequeño círculo) y cada segmento s= {[pic] } se representa por una curva que conecta sus terminales [pic].
TIPO DE GRAFOS
Gráficamente los vértices se representan por círculos, las líneas (o aristas) pertenecen alos grafos no dirigidos y las flechas (o arcos) a los grafos dirigidos. Existen dos tipos de grafos los dirigidos y los no dirigidos:
* Un dígrafo o grafo dirigido.- Es un par D = (V, E) consistente en un conjunto finito no vacío V cuyos miembros se llaman vértices y una familia finita E de pares ordenados de vértices a cuyos elementos llamaremos aristas o arcos. Al par (u, v) ∈E lodenotaremos por uv y diremos que u es el extremo inicial y que v es el extremo final. Son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi, Vj >!=<Vj, Vi>. En grafos dirigidos, para cada lado <A, B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual esel vértice destino, se conoce como cabeza del lado. 
Un grafo dirigido (o dígrafo) consta de:
1. un conjunto finito de vértices V
2. un conjunto de arcos E V × V (obsérvese que cada arco es un par ordenado vértices)
Este es un ejemplo de un grafo dirigido


* No dirigidos: Son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entreparéntesis, separando sus vértices por comas. Son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

TIPO ESPECIALES DE GRAFOS
a) Un grafo regular de grado n si todos sus vértices tienen grado n.

b) Se dice que un grafo es completo cuando todos sus vértices...