Resumenes y ensallos

Solo disponible en BuenasTareas
  • Páginas : 3 (658 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de mayo de 2011
Leer documento completo
Vista previa del texto
trabajo de investigacion de los grafos

Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muydiversa índole. Un grafo simple está formado por dos conjuntos:
Un conjunto V de puntos llamados vértices o nodos.

Tipos de grafos
Existen dos tipos de grafos los no dirigidos y los dirigidos.• No dirigidos: 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).
• Dirigidos: 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 !=. En grafosdirigidos, para cada lado , A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.
Ejemplo:
La imagen es una representacióndel siguiente grafo:
• V:={1,2,3,4,5,6}
• E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
Representación matricial
Éste es un procedimiento para decidir cuándo una proposición dada en FC es o nocontradicción

Caminos y circuitos
Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso
• x e y sellaman los extremos del camino
• El número de aristas del camino se llama la longitud del camino.
• Si los vértices no se repiten el camino se dice propio o simple.
• Si hay un camino no simple entre2 vértices, también habrá un camino simple entre ellos.
• Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
• Llamaremos ciclo a un circuito simple
•Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

Isomorfismo

Dos grafos G1 y G2 son isomorfos si existe una...
tracking img