Arboles y graficass

Solo disponible en BuenasTareas
  • Páginas : 10 (2470 palabras )
  • Descarga(s) : 0
  • Publicado : 14 de diciembre de 2009
Leer documento completo
Vista previa del texto
GRAFO
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (arcs 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).
El grado o valencia
de un vértice es el número de aristasincidentes en él. Para un grafo con bucles, éstos son contados por dos.
TEOREMA DE EULER
En un grafo conexo podemos encontrar un circuito de Euler si solo si, cuando todas sus valencias son pares.


Un grafo conexo tiene un camino de Euler si solo si todas sus valencias son pares, excepto dos.
EJEMPLO DE GRAFO PARA LOS RECORRIDOS Y CAMINOSRecorrido:
Secuencia de aristas consecutivas.
(A, B), (B, C), (C, D), (D, G)
Recorrido cerrado:
Si termina donde empieza.
(A, B), (B, E), (E, A)
Camino:
Recorrido que tiene aristas distintas.
(A, B), (B, C), (C, F), (F, B)
Camino cerrado:
Termina donde empieza.
(A, B), (B, E), (E, A)
Camino simple: Si no utiliza dosveces un mismo nodo, ni tampoco la misma arista.
CIRCUITO DE HAMILTON
Es un camino simple cerrado que utiliza todos los nodos.
(A, B), (B, C), (C, D), (D, G), (G, I), (I, F), (F, H), (H, E), (E, A)
Ejemplo de grafo para camino de Hamilton
CAMINO DE HAMILTON
Es un camino simple que utiliza todos los nodos.
(A, C), (C, E), (E, D), (D,B)

Tipos de grafos
Existen dos tiposde 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 porcomas 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 es el vértice destino, se conoce como cabeza del lado.

Se dice que el grafo G = (V, E) es
a) Un grafo regular de grado n si todos sus vértices tienen grado n.
b) Un grafo completo si cada par de vértices estáunido por una arista. Se denota por Kn al grafo completo de n vértices
c) Un ciclo si V = {v1, v2, . . . vn}, n³> 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1)}. Se denota por Cn al ciclo de n vértices
d)Una rueda si V = {v0, v1, v2, . . . vn}, n n> 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1), {(v1, v0), (v2, v0), . . . , (vn, v0) }. Se denota por Wn a la rueda de n+1 vértices
e)Un cubosi sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Qn al cubo asociado al cubo n-dimensional.
f)Un grafo bipartido si V=V 1 UV 2 y cada arista de E une un vértice de V1 y otro de V2
g)Un grafo bipartido completo si V=V 1 UV 2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s algrafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices

NODOS
Un nodo es un elemento constitutivo del hipertexto que contiene una cantidad discreta de información. Nodo es cada elemento que forma parte de la red de información y que puede corresponder bien con las definiciones clásicas de un documento escrito: capítulos, secciones, párrafos, etc; bien con las definiciones nacidasal albur del mundo digital: porción de texto contenido en la ventana de la pantalla, archivo individual, etc.

Aplicaciones de los Nodos
Un nodo es un segmento de información que entra en relación con otro u otros nodos. Cada nodo pertenece únicamente a un documento, que puede estar formado por uno o varios nodos. Los nodos son, pues, los elementos que contienen la información o las unidades...
tracking img