Unidad IV Matem Tica Discreta

Unidad 4.
Integrantes:
Ana Sanabria. C.I 24.337.869
Ludwing Sahmkow
21.534.308
Enderson Quintana
20.114.448
Freymi Jimenez 19.388.596

Grafo Euleriano.
Son aquellos que pueden
recorrerse completamente desde
un vértice y regresar al punto de
origen sin pasar dos veces por la
misma arista.

El nombre de este tipo
de grafos proviene del
matemático Leonard
Euler quien abordó por
primera vez elasunto de
cómo debían
caracterizarse los grafos
para poder recorrerse de
la manera deseada tras
desestimar el problema
de los puentes de
Königsberg.

Casos particulares.
Un grafo G= no dirigido y conexo que tiene exactamente
2 vértices de grado impar, entonces tiene un camino euleriano
no cerrado.
Un grafo G= no dirigido y conexo cuyos vértices tienen
grado par, entonces tiene un cicloeuleriano.

Teorema General.
Sea un grafo G= no dirigido y conexo, entonces las expresiones
siguientes equivalen:
G es grafo euleriano.
Todos sus vértices tienen grado par no nulo.

Propiedades.
Un grafo conexo y no dirigido se dice que es euleriano si cada vértice
tiene un grado par.
Un grafo no dirigido es euleriano si es conexo y si se puede
descomponer en uno con los vértices disjuntos.
Si ungrafo no dirigido G es euleriano entonces su gráfo-línea L(G) se
dice que es también euleriano.
Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados
internos iguales a los externos.
Un grafo no dirigido se dice que es susceptible de ser recorrido (en
inglés: traversable) si es conexo y al menos dos vértices en el grafo
tienen grado impar.

Grafos Hamiltonianos.
Es cuándo ungrafo tiene un ciclo
cerrado que contiene a todos sus
vértices y cuándo es posible hacer un
recorrido en un grafo que pase por
cada vértice exactamente una vez y
termine en el vértice original.

Se llaman así en honor
de William Rowan
Hamilton, inventor de un
juego que consistía en
encontrar un ciclo
hamiltoniano en las
aristas de un grafo de un
dodecaedro. Hamilton
resolvió este problemausando cuaterniones,
aunque su solución no
era generalizable a todos
los grafos.

Distancia en un Grafo.
Es el número de vértices mínimo que debe recorrerse para
unirlos. La distancia entre dos nodos de un grafo es la
longitud del camino más. Si no hubiera conexión alguna
entre dos vértices se dice que la distancia es infinita. Las
distancias de todos los vértices de un grafo se computan en
lo que sedenomina matriz de distancias. El concepto se
emplea en las mediadas de centralidad de redes.

Red de nodos mostrando los
divisores. En el grafo se
puede ver que la distancia
entre 1 y 6 es 1 debido a que
puede recorrerse de forma
mínima tanto por 1-2-6 como
por 1-3-6. De la misma forma
la distancia entre 1 y 12 es 2
de cualquier forma.

Existen numerosas aplicaciones en la teoría de grafos en las queinterviene el concepto de distancia, por ejemplo en el diseño de
grandes interiores, tales como los aeropuertos donde el concepto
distancia supone el conocimiento del tiempo necesario para llegar a
un punto cualesquiera del mismo. Es uno de los conceptos clave en
las redes de mundo pequeño.

Arboles.
Un árbol es un grafo no dirigido
conexo que no contiene
circuitos, es decir que no
existen dos omás paseos sobre
un par de vértices. Un conjunto
de árboles disjuntos es llamado
bosque. Un vértice de grado 1
en un árbol se llama hoja o un
nodo terminal, y un vértice de
grado mayor que 1 recibe el
nombre de rama o nodo
interno. Por ejemplo, son hojas:
b, c, d y los vértices a, A, B, C,
D son nodos rama.

Un claro ejemplo de un árbol
es el siguiente:
Consideremos cuatro parejas
de chismosos {a,A, b, B, c, C,
d, D} donde a, b, c y d son los
esposos y A, B, C y D son sus
esposas respectivamente.
Supongamos que a llama a su
esposa para contarle algún
chisme, entonces ella llama a
las otras señoras para difundir
el chisme, y cada una de ellas
a su vez llama a su esposo
para comunicárselo.

Propiedades.
* Existe un único paseo entre dos vértices cualesquiera de un árbol.
* El número de...

Leer documento completo

Regístrate para leer el documento completo.