MDyL2 GRAFOS

MATEMÁTICA DISCRETA Y LÓGICA 2
Prof.: FERNANDO GERFAUO.
TECNÓLOGO EN INFORMÁTICA.
Sede: PAYSANDÚ.
AÑO 2019.-
Tecnólogo en Informática
Sede Paysandú
Matemática Discreta y Lógica II. Segundo semestre .
Conceptos básicos de la Teoría de Grafos

• Definiciones
• Subgrafo, complementos, isomorfismoTEMARIO- BIBLIOGRAFÍA
• Grado de un vértice, circuitos y recorridos Eulerianos

• Ciclos y caminos Hamiltonianos
• Árboles
Lógica de predicados
• Cuantificadores
• Estructuras
• Semántica básica
• Propiedades básicas de la Lógica de Predicados
Bibliografía:
•Logic and Structure. Dirk van Dalen. Ed. Springer-Verlag.
•Matemáticas Discreta y Combinatoria. Ralph P. Grimaldi. Ed. Addison Wesley
Prof.: Fernando Gerfauo Año 2019.-
Sede Paysandú
GRAFO DIRIGIDO
Grafo dirigido.
Sean Ⅴ un conjunto no vacío y A un conjunto incluido en ⅤxⅤ.
Se denomina grafo dirigido en Ⅴ o digrafo en Ⅴ, al par ordenado (V, A).

Notación: 𝖦=(Ⅴ, A)

El conjunto Ⅴ recibe el nombre de conjunto de vértices o nodos del
digrafo, mientras que el conjunto A se llama conjunto de las aristas del
digrafo.

Sede Paysandú
Sea (a, b) una arista de un digrafo 𝖦.

Los extremos de la arista son los vértices “a” y “b”, siendo “a” el vértice
TERMINOLOGÍA
inicial de la arista y “b” el vértice final.
Se dice que la arista (a, b) es incidente con los vértices “a” y “b”.
También se dice que el vértice “a” es adyacente hacia el vértice “b”, y

que el vértice “b” es adyacente desde el vértice “a”.
Cuando un vértice no tiene aristas incidentes, se denomina vértice

aislado.
Una arista de la forma (a, a) se llama lazo o bucle.

Sede Paysandú
Grafos de influencias.
Algunos EJEMPLOS
Construye un grafo de influencias para la junta directiva de una empresa

donde el presidente puede influir en el director de investigación, en el
director de marketing y en el director de operaciones.
El director de investigación puede influir en el director de operaciones;
el director de marketing puede influir en el director de operaciones, y
nadie puede influir en el director financiero ni tampoco puede ser
influido por él.
Fuente:
Rosen, K. (2004). “Matemática Discreta y sus Aplicaciones”. Quinta Edición.
McGRAW-HILL/Interamericana de España. Madrid.

Sede Paysandú
Grafos de precedencia y procesamiento concurrente.

Los programas informáticos pueden ejecutarse más rápidamente si
ciertas sentencias se ejecutan simultáneamente.Algunos EJEMPLOS
Es importante no ejecutar sentencias que requieran el resultado de

sentencias aún no ejecutadas.
La dependencia de sentencias con respecto a sentencias previas se
puede representar por medio de un grafo dirigido denominado grafo de
precedencia.
Cada sentencia se representa por un vértice, y hay una arista de un
vértice a un segundo vértice, si la sentencia representada por el segundo
vértice no puede ejecutarse hasta que la sentencia representada por el
primero haya sido ejecutada.
Fuente: Rosen, K. (2004). “Matemática Discreta y sus Aplicaciones”. Quinta Edición.
Sede Paysandú
El grafo de la Red.
La Red de Internet (en inglés, World Wide Web) se puede representar
Algunos EJEMPLOS
por medio de un grafo dirigido en el que cada página web está

representada por un vértice, y en el que una arista comienza en la
página “a” y termina en la página “b” si hay un enlace en la página “a”
que conduce a la página “b”.
Como se crean páginas web nuevas a cada segundo mientras que otras
desaparecen, el grafo de la Red se encuentra en estado de cambio
perpetuo.
Muchas son las personas que estudian las propiedades del grafo de la
Red para entender mejor la naturaleza de la Red de Internet.
Fuente: Rosen, K. (2004). “Matemática Discreta y sus Aplicaciones”. Quinta Edición.
Sede Paysandú
Cuando no importa la dirección de las aristas, la estructura 𝖦=(Ⅴ, A),

donde A es ahora un conjunto de pares no ordenados sobre Ⅴ, recibe el
GRAFO (no dirigido)
nombre de grafo no dirigido.
Observación:
Cuando no se especifica si un grafo es dirigido o no, se supondrá que es
no dirigido.
Una arista {a, b} de un grafo 𝖦=(Ⅴ, A) representa a {(a, b), (b, a)}.
Se tiene que {a, b} = {b, a}.
Se dice que los vértices “a” y “b” son adyacentes.
Para designar un lazo en un grafo no dirigido se escribe {a, a}; pero
{a, a} se considera igual a (a, a).
Sede Paysandú
Camino.
Sea 𝖦=(Ⅴ, A) un grafo. Se dice que hay un camino en 𝖦 que va de un
CAMINOS EN UN GRAFO
vértice “x” hasta un vértice “y”, si existe una sucesión alternada y finita
de vértices y aristas (sin lazos) de 𝖦 como:
x, {x, x1}, x1 , {x1, x2}, x2, …, xn-1, {xn-1, xn}, xn = y, siendo xi ∈Ⅴ, ∀i, i∈ℕ*.

Notación: x - y
Longitud de un camino: el número de aristas de un camino, recibe el
nombre de longitud del camino.
Se dice que un camino es trivial cuando el número de aristas es 0.
Cualquier camino x - y donde x = y, con al menos dos aristas, se llama
camino cerrado. En caso contrario, el camino es abierto.
Sede Paysandú
Sea 𝖦=(Ⅴ, A) un grafo.

Camino simple. Un camino simple en 𝖦 es un camino x – y que no
CAMINOS EN UN GRAFO
repite vértices (salvo que “x” coincida con “y”).

Recorrido. Se llama recorrido en 𝖦 de un vértice “x” hasta un vértice “y”,
a todo camino x – y en 𝖦 que no repite aristas.
Circuito. Se llama circuito en 𝖦 a todo recorrido cerrado.
Ciclo. Se denomina ciclo en 𝖦 a todo camino simple cerrado.
Convenciones:
Un circuito tiene al menos una arista. Si tiene una sola arista el circuito es
un lazo. Si tiene dos aristas el circuito se da en un multigrafo.
Un ciclo implica siempre la presencia de al menos tres aristas distintas
del grafo.
Sede Paysandú
CAMINOS EN UN GRAFO
Teorema:
Sea 𝖦=(Ⅴ, A) un grafo, con x, y ∈ Ⅴ, x≠ y.
Si existe un recorrido en 𝖦 de x hasta y, entonces existe un camino
simple en 𝖦 de x hasta y.

Sede Paysandú
Grafo conexo.
Se dice que un grafo 𝖦=(Ⅴ, A) es conexo, si para cada par de
GRAFO CONEXO
vértices diferentes de 𝖦, existe un camino simple que los conecta.

Un digrafo 𝖦=(Ⅴ, A) es conexo, si es conexo su grafo sostén.
Grafo disconexo.
Si un grafo no es conexo, se dice que es disconexo.
Observación:
Un grafo disconexo está compuesto por dos o más “piezas” que son
conexas, que reciben el nombre de componentes conexas del grafo.
El número de componentes conexas de un grafo 𝖦 se denota con κ(𝖦).
Sede Paysandú
Multigrafo.
Un grafo 𝖦=(Ⅴ, A) es un multigrafo, si existen vértices a y b diferentes
MULTIGAFO
de Ⅴ, con dos o más aristas de la forma:
• (a, b) para un digrafo.
• {a, b} para un grafo.
Si en un multigrafo existen n aristas de a a b, con n∈ℕ y n ≥ 2, se

dice que la arista tiene multiplicidad n.
Observación: cuando se trabaje con un multigrafo 𝖦, se establecerá

explícitamente que 𝖦 es un multigrafo.
Sede Paysandú
Subgrafo.
Sea 𝖦=(Ⅴ, A) un grafo (dirigido o no). SUBGRAFOS
Se dice que 𝖦’=(Ⅴ’, A’) es un subgrafo de 𝖦, si Ⅴ’≠∅, Ⅴ’⊆ V y A’⊆ A,

donde cada arista de A’ es incidente con los vértices de Ⅴ’.
Subgrafo recubridor.
Sea 𝖦=(Ⅴ, A) un grafo (dirigido o no).
Un subgrafo 𝖦’ =(Ⅴ’, A’) de 𝖦, se llama subgrafo recubridor si Ⅴ’ = V.
Pregunta:
Si 𝖦=(Ⅴ, A) es un grafo con n aristas, ¿cuántos subgrafos recubridores
tiene 𝖦?
Sede Paysandú
Subgrafo inducido.
Sea 𝖦=(Ⅴ, A) un grafo (dirigido o no) y sea U, un conjunto no vacío, tal
SUBGRAFOS
que U ⊆ V.
El subgrafo de 𝖦 inducido por U, es el subgrafo cuyo conjunto de
vértices es U y que contiene todas las aristas de 𝖦, de la forma (a, b)
para a, b ∈ U si 𝖦 es dirigido, o de la forma {a, b} para a, b ∈ U si 𝖦 no
es dirigido.
Notación: <U>
Observación:
𝖦’ es subgrafo inducido de 𝖦=(Ⅴ, A) si existe un conjunto U, U’≠∅,
U ⊆ V, tal que 𝖦’= <U>
Sede Paysandú
Subgrafo 𝖦 – v.
Sea v un vértice de un grafo 𝖦=(Ⅴ, A) dirigido o no.
SUBGRAFOS
El subgrafo 𝖦 – v de 𝖦 es el subgrafo de 𝖦 que tiene por conjunto de

vértices a Ⅴ’ = V- {v}, y por conjunto de aristas a A’⊆ A, tal que A’
contiene todas las aristas de A, salvo los incidentes con el vértice v.
Observación: 𝖦 – v es el subgrafo de 𝖦 inducido por Ⅴ’ = V- {v}.
Subgrafo 𝖦 – a.
Sea a una arista de un grafo 𝖦=(Ⅴ, A) dirigido o no.
El subgrafo 𝖦 – a de 𝖦, es el subgrafo de 𝖦 que tiene por conjunto de
vértices a V y por conjunto de aristas a A’ = A- {a}.
Observación: 𝖦 – a es un subgrafo recubridor de 𝖦=(Ⅴ, A).
Sede Paysandú
Grafo completo.
Sea V un conjunto con n vértices, n∈ℕ*.
Se llama grafo completo en V, y se lo denota con Kn, a un grafo sin lazos
GRAFOS “DISTINGUIDOS”
en el que, para cualquier par de vértices diferentes, existe una arista que
los conecta.
Grafo complemento.
Sea 𝖦=(Ⅴ, A) un grafo sin lazos, con n vértices, n∈ℕ*.
El grafo complementario de 𝖦 es el grafo Ḡ=(Ⅴ, Ā), donde Ā tiene
todas las aristas de Kn que no están en A.
Grafo nulo.
Si 𝖦 = Kn, entonces Ḡ es un grafo con n vértices y ninguna arista. Dicho
grafo se denomina grafo nulo.
Sede Paysandú
Grafo bipartito.
Un grafo 𝖦=(Ⅴ, A) es un grafo bipartito, si el conjunto Ⅴ puede ser
GRAFOS “DISTINGUIDOS”
particionado en dos subconjuntos disjuntos V1 y V2, tal que cada arista de

𝖦 tiene un extremo en V1 y otro en V2.
Grafo bipartito completo.

Si cada vértice de V1 está conectado con los vértices de V2, entonces el
grafo 𝖦 es un grafo bipartito completo.
Notación:
Si la cantidad de vértices de V1 es m y la cantidad de vértices de V2 es n,
el grafo bipartito completo se denota con Km, n.
Sede Paysandú
Grado de un vértice.
Sea 𝖦 un grafo o multigrafo.
GRADO DE UN VÉRTICE
El grado de un vértice v de 𝖦, que se denota con gr(v), es el número de

aristas en 𝖦 que son incidentes con v.
Un lazo incidente en v se considera como dos aristas incidentes en v.
Teorema:
Si 𝖦 es un grafo o multigrafo, entonces se tiene que la suma de los
grados de sus vértices es igual al doble del número de sus aristas.
Corolario:
Si 𝖦 es un grafo o multigrafo, la cantidad de vértices de grado impar
es par.
Sede Paysandú
Grafo regular. GRAFO k-REGULAR
Se dice que un grafo (o multigrafo) es regular cuando todos sus vértices

tienen el mismo grado.
Grafo k-regular.
Se dice que un grafo es k-regular si todos los vértices del grafo tienen
grado k.

Sede Paysandú
Isomorfismo de grafos.
Sean G1=(Ⅴ1, A1) y G2=(Ⅴ2, A2) dos grafos. Se llama isomorfismo entre
los grafos G1 y G2, a toda función f: V1 →V2, tal que:
ISOMORFISMOS DE GRAFOS
1) f es biyectiva.
2) Para todos a ∈ V1, b ∈ V1, la arista {a, b} ∈ A1 si y sólo si,
la arista {f(a), f(b)} ∈ A2.
Grafos isomorfos.
Cuando existe un isomorfismo entre dos grafos, se dice que los grafos
son isomorfos.
Observación: cuando dos grafos son isomorfos, es porque existe una

función biyectiva entre los vértices de los dos grafos, que preserva la
relación de adyacencia.
Sede Paysandú
En general, resulta difícil determinar si dos grafos son isomorfos o no.

Hay n! posibles funciones biyectivas entre los conjuntos de vértices de
dos grafos de n vértices. Chequear cada una de estas funciones para ver
ISOMORFISMOS DE GRAFOS
si preservan o no las adyacencias, resulta poco práctico cuando n es muy

grande.
Sin embargo, se puede demostrar que dos grafos no son isomorfos,
reconociendo que no comparten alguna propiedad que dos grafos
isomorfos deberían de cumplir. Tales propiedades, reciben el nombre de
invariantes.
Por ejemplo, el número de vértices y la cantidad de aristas, son
invariantes bajo isomorfismos de grafos (¿por qué?).
Cabe aclarar que, aunque esos invariantes coincidan, los grafos no tienen
que ser necesariamente isomorfos.

Sede Paysandú
La ciudad de Königsberg, hoy Kaliningrado, perteneciente al territorio

ruso, está situada en las márgenes del Río Pregel y sobre dos de sus islas.
CIRCUITOS Y RECORRIDOS EULERIANOS
Las distintas partes de la ciudad están conectadas entre ellas por siete
puentes. Los domingos, la gente de la ciudad, solía dar un paseo, y
entonces surgió la pregunta: ¿es posible efectuar un paseo a pie, tal que
utilizando exactamente una vez cada uno de los puentes, se vuelva al
punto inicial?
Nota: Este fue el primer problema, en orden cronológico, de los resueltos con métodos
actualmente incluidos en la Teoría de Grafos. Su autor fue el matemático L. Euler (1707-1783).
Sede Paysandú
¿Podemos movernos por las aristas de un grafo comenzando en un

vértice y volviendo a él, después de haber pasado por cada arista del
grafo exactamente una vez?
Definiciones:
Sea 𝖦=(Ⅴ, A) un grafo (o multigrafo) sin vértices aislados.
Un circuito euleriano en 𝖦 es un circuito que contiene a todas las aristas

de 𝖦. Es decir, un circuito euleriano en 𝖦 es un circuito que
recorre cada arista del grafo 𝖦 (exactamente una vez).
Un recorrido euleriano en 𝖦 es un recorrido abierto que contiene a

todas las aristas de 𝖦.
Sede Paysandú
Teorema.
𝖦 tiene un circuito euleriano, si y sólo si 𝖦=(Ⅴ, A) es conexo y todo

vértice de 𝖦 tiene grado par.
Corolario.
𝖦 tiene un recorrido euleriano, si y sólo si 𝖦=(Ⅴ, A) es conexo y tiene
exactamente dos vértices de grado impar.
Observación:
El teorema y su corolario, establecen condiciones necesarias y suficientes
para la existencia de circuitos y recorridos eulerianos en un grafo 𝖦.
Sede Paysandú
Se debe a los trabajos del matemático irlandés Sir Wiliam R. Hamilton

(1805-1865), la existencia en los grafos, de lo que hoy se denominan
CICLOS Y CAMINOS HAMILTONIANOS
ciclos hamiltonianos.
En 1859, Hamilton inventó un juego, llamado “Icosian Game” que
consistía en un dodecaedro regular de madera
con 20 vértices en los que aparecían inscritos
los nombres de ciudades importantes:
Bruselas, Cantón, Delhi, Frankfurt, etc.
El jugador debía encontrar un recorrido a lo
largo de las aristas del dodecaedro, que pase
exactamente una vez por cada ciudad, y volver
a la ciudad de la cual se partió.

Sede Paysandú
Definiciones.
Sea 𝖦=(Ⅴ, A) un grafo (o multigrafo) con 3 o más vértices.
CICLOS Y CAMINOS HAMILTONIANOS
Un ciclo hamiltoniano en 𝖦 es un ciclo de 𝖦 que contiene a cada uno de

los vértices de 𝖦.
Un camino hamiltoniano en 𝖦 es un camino simple (y no un ciclo) de 𝖦

que contiene todos los vértices de 𝖦.
Observación:
A diferencia de los que ocurre con los circuitos y recorridos eulerianos, no
existen condiciones necesarias y suficientes que garanticen la existencia de
un ciclo (o de un camino) hamiltoniano en un grafo 𝖦.
Sede Paysandú
Si bien existen teoremas que establecen condiciones necesarias o

suficientes para que un grafo tenga un ciclo o un camino hamiltoniano
(ver bibliografía sugerida), a la hora de buscar ciclos (caminos) en grafos
CICLOS Y CICLOS HAMILTONIANOS
particulares, se recurre frecuentemente al método de ensayo y error.

En tal caso, las siguientes sugerencias pueden resultar útiles:
• Si 𝖦=(Ⅴ, A) tiene un ciclo hamiltoniano, entonces gr(v) 2, ∀v, v ∈ Ⅴ.
• Si a ∈ Ⅴ y gr(a)=2, entonces las dos aristas incidentes en el vértice a

deben formar parte de cualquier ciclo hamiltoniano.
• Si a ∈ Ⅴ y gr(a) >2, entonces cuando se trata de construir un ciclo

hamiltoniano, una vez que se ha pasado por el vértice a, se dejan de
tener en cuenta las aristas no utilizadas incidentes con a.
Sede Paysandú
El concepto de Árbol fue utilizado por primera vez por el físico prusiano
Gustav Kirchhoff (1824-1887) con el fin de simplificar la resolución de
sistemas de ecuaciones lineales que se tratan en redes eléctricas.
ÁRBOLES
El químico inglés Arthur Cayley (1821-1895), investigando

el número de hidrocarburos con enlaces simples que
responden a la fórmula CnH2n+2, donde “n” es el número
de átomos de carbono, vuelve a definir el concepto de
Árbol y lo desarrolla.

Con el surgimiento de las computadoras digitales, algunos tipos
especiales de árboles resultaron trascendentes al estudiar estructuras de
datos, algoritmos de ordenamiento, teoría de codificación, y en la
solución de ciertos problemas de optimización.
Sede Paysandú
Definición.
Sea 𝖦=(Ⅴ, A) un grafo sin lazos. ÁRBOLES
El grafo 𝖦 es un árbol, si 𝖦 es conexo y no contiene ciclos.
Notación:
Si un grafo 𝖦 es un árbol, se escribe T en vez de 𝖦, para enfatizar esta
estructura.
Ejemplos.

Sede Paysandú
Teorema.
Sea T=(Ⅴ, A) un árbol. Si a y b son dos vértices diferentes de T, entonces
existe un único camino simple que conecta estos vértices.
ÁRBOLES
Teorema.
Sea G=(Ⅴ, A) un grafo sin lazos. G es conexo si y sólo si 𝖦 tiene un árbol
recubridor.
Un árbol recubridor de un grafo 𝖦 es un subgrafo recubridor de 𝖦 que

también es árbol.
Teorema.
Si T=(Ⅴ, A) es un árbol, entonces se cumple que |Ⅴ| = |A| + 1.

Sede Paysandú
Teorema.
Sea T=(Ⅴ, A) un árbol. Si a y b son dos vértices diferentes de T, entonces
existe un único camino simple que conecta estos vértices.
ÁRBOLES
Teorema.
Sea G=(Ⅴ, A) un grafo sin lazos. G es conexo si y sólo si 𝖦 tiene un árbol
recubridor.
Un árbol recubridor de un grafo 𝖦 es un subgrafo recubridor de 𝖦 que

también es árbol.
Teorema.
Si T=(Ⅴ, A) es un árbol, entonces se cumple que |Ⅴ| = |A| + 1.

Sede Paysandú
Forma alternativa del Principio de Inducción Matemática.

Sea P(n) una proposición matemática abierta (o un conjunto de tales
INDUCCIÓN MATEMÁTICA
proposiciones abiertas) donde la variable n que representa a un número

natural no nulo, aparece una o más veces. Además, sean n0 y n1 naturales
tales que n0 ≤ n1.
a) Si P(n0), P(n0+1), P(n0+2), …, P(n1-1) y P(n1) son verdaderas, y

b) siempre que P(n0), P(n0+1), …, P(k-1) y P(k) sean verdaderas para algún
k, k∈ℕ, donde k ≥ n1, entonces la proposición P(k+1) también es
verdadera.
Entonces, P(n) es verdadera para todo n ≥ n0.

Sede Paysandú
Definición.
Sea G=(Ⅴ, A) un grafo dirigido. ÁRBOL CON RAÍZ
Si el grafo no dirigido asociado a G es un árbol, entonces G es un árbol

dirigido.
Definición.
Sea T=(Ⅴ, A) un árbol dirigido.
T es un árbol con raíz, si existe un único vértice en T cuyo grado de
entrada es nulo, y todos los demás vértices de T tienen grado de entrada
1.
El vértice de T cuyo grado de entrada es nulo, recibe el nombre de raíz
del árbol dirigido.
Sede Paysandú
Definiciones.
Sea T=(Ⅴ, A) un árbol con raíz.
• Todo vértice de T cuyo grado de salida es nulo, recibe el nombre de
ÁRBOL CON RAÍZ
hoja del árbol.

• Los demás vértices de T se denominan nodos de ramificación o
vértices internos del árbol.
• Padre.
• Hijo.
• Hermano.
• Descendientes.
• Ascendientes.
• Subárbol.

Sede Paysandú
Definiciones.
Sea T=(Ⅴ, A) un árbol con raíz y m ∈ ℕ*.
ÁRBOL CON RAÍZ m-ario
T es un árbol m-ario si el grado de salida de todo vértice de T es, a lo

sumo, m. En el caso particular en que m = 2, el árbol recibe el nombre
de árbol binario.
T es un árbol m-ario completo si el grado de salida de todo vértice de T

es 0 o m. En el caso especial en que m = 2, se tiene un árbol binario
completo.
Observación:
En un árbol m-ario completo cada vértice interno tiene exactamente m hijos.

Sede Paysandú
Teorema.
Sea T=(Ⅴ, A) un árbol m-ario completo con n vértices.
Si T tiene h hojas e i vértices internos, entonces se cumple que:
ÁRBOL CON RAÍZ m-ario
a)
b)
c)
d)

Sede Paysandú
Definición.
Un árbol ordenado con raíz es un árbol con raíz en el que los hijos de
ÁRBOL ORDENADO CON RAÍZ
cada vértice interno están ordenados.
Los árboles ordenados con raíz se dibujan de modo que los hijos de los
vértices internos se colocan ordenados de izquierda a derecha.
Existen diferentes métodos para la ordenación sistemática de los vértices

de un árbol. Dos de los más importantes en el estudio de las estructuras
de datos son el orden previo y el orden posterior.
Sede Paysandú
Sea T=(Ⅴ, A) un árbol con raíz r.
• Si |V|= 1, entonces r es el recorrido en orden previo y orden posterio

ÁRBOL ORDENADO CON RAÍZ
de T.
• Si |V| > 1, sean T1, T2, …, Tk, los subárboles de T, de izquierda a

derecha.
a) El recorrido en orden previo de T, visita primero la raíz r y después
recorre los vértices de T1 en orden previo, luego los vértices de T2
en orden previo, y así sucesivamente, hasta recorrer los vértices de
Tk en orden previo.
b) El recorrido en orden posterior de T, recorre en orden posterior los
vértices de los subárboles T1, T2, …, Tk, para después llegar a r.
Sede Paysandú
Búsqueda en profundidad.
Sea G=(Ⅴ, A) un grafo conexo con r ∈ Ⅴ. A partir de r, se construye un camino

ALGORITMOS DE BÚSQUEDA
simple en G lo más largo posible. Si este camino incluye todos los vértices de Ⅴ,
entonces el camino simple es un árbol recubridor T de G, concluyendo la
búsqueda. En caso contrario, sean x e y los últimos dos vértices visitados por el
camino, con y como último vértice. Se retrocede al vértice x y se construye un
segundo camino simple en G, lo más largo posible, a partir de x, que no incluya
a los vértices ya visitados. Si no existe tal camino, se retrocede al padre p de x,
y se construye, partir de p, un camino simple lo más largo posible, que excluya
los vértices ya visitados, hasta llegar a una nueva hoja y1.
En caso de que todas las aristas que parten de p conduzcan a vértices ya
visitados, se retrocede un nivel más y se continua con el proceso.
Puesto que el grafo G es finito y conexo, esta técnica, llamada búsqueda en
profundidad, determinará un árbol recubridor T de G, cuya raíz es r.
Sede Paysandú
Búsqueda en profundidad.
Sea G=(Ⅴ, A) un grafo conexo, sin lazos, tal que |V|= n, y donde los vértices
están ordenados como v1, v2, v3, …, vn. Para encontrar el árbol recubridor en
profundidad, ordenado con raíz, se aplica el siguiente algoritmo, donde se

utiliza la variable v para guardar el vértice que se analiza en un momento dado.
Paso 1: Se asigna v1 a la variable v y se inicializa T como el árbol que consta
solamente de este vértice.
Paso 2: Se selecciona el subíndice más pequeño i, 2 ≤ i ≤ n, tal que {v, vi} ∈ A
y vi no ha sido visitado todavía. Si no se encuentra tal subíndice, entonces se va
al Paso 3. En caso contrario, se procede como sigue: 1) se añade la arista {v, vi}
al árbol T; 2) se asigna vi a v; y 3) se regresa al Paso 2.
Paso 3: Si v = v1 , el árbol T es el árbol recubridor (ordenado, con raíz) del orden
dado.
Paso 4: Si v ≠ v1 , se retrocede desde v. Si p es el padre del vértice asignado a v
en T, entonces se asigna p a v y se regresa al Paso 2.
Sede Paysandú
Búsqueda en anchura.

Sede Paysandú
Matemática Discreta y Lógica II. Segundo semestre.
BIBLIOGRAFÍA CONSULTADA:
Año 2019.-

MDyL2 GRAFOS

Cargado por

Copyright:

Formatos disponibles

MDyL2 GRAFOS

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

MDyL2 GRAFOS

Cargado por

Copyright:

Formatos disponibles

MATEMÁTICA DISCRETA Y LÓGICA 2

Prof.: FERNANDO GERFAUO.

Conceptos básicos de la Teoría de Grafos

• Grado de un vértice, circuitos y recorridos Eulerianos

Prof.: Fernando Gerfauo Año 2019.-

Sea (a, b) una arista de un digrafo 𝖦.

inicial de la arista y “b” el vértice final.

También se dice que el vértice “a” es adyacente hacia el vértice “b”, y

Cuando un vértice no tiene aristas incidentes, se denomina vértice

Una arista de la forma (a, a) se llama lazo o bucle.

Construye un grafo de influencias para la junta directiva de una empresa

Prof.: Fernando Gerfauo Año 2019.-

Grafos de precedencia y procesamiento concurrente.

Es importante no ejecutar sentencias que requieran el resultado de

por medio de un grafo dirigido en el que cada página web está

Cuando no importa la dirección de las aristas, la estructura 𝖦=(Ⅴ, A),

nombre de grafo no dirigido.

Sea 𝖦=(Ⅴ, A) un grafo.

repite vértices (salvo que “x” coincida con “y”).

Prof.: Fernando Gerfauo Año 2019.-

vértices diferentes de 𝖦, existe un camino simple que los conecta.

de Ⅴ, con dos o más aristas de la forma:

• (a, b) para un digrafo.

• {a, b} para un grafo.

Si en un multigrafo existen n aristas de a a b, con n∈ℕ y n ≥ 2, se

Observación: cuando se trabaje con un multigrafo 𝖦, se establecerá

Se dice que 𝖦’=(Ⅴ’, A’) es un subgrafo de 𝖦, si Ⅴ’≠∅, Ⅴ’⊆ V y A’⊆ A,

El subgrafo 𝖦 – v de 𝖦 es el subgrafo de 𝖦 que tiene por conjunto de

particionado en dos subconjuntos disjuntos V1 y V2, tal que cada arista de

Grafo bipartito completo.

El grado de un vértice v de 𝖦, que se denota con gr(v), es el número de

Grafo regular. GRAFO k-REGULAR

Se dice que un grafo (o multigrafo) es regular cuando todos sus vértices

Prof.: Fernando Gerfauo Año 2019.-

Observación: cuando dos grafos son isomorfos, es porque existe una

En general, resulta difícil determinar si dos grafos son isomorfos o no.

si preservan o no las adyacencias, resulta poco práctico cuando n es muy

Prof.: Fernando Gerfauo Año 2019.-

La ciudad de Königsberg, hoy Kaliningrado, perteneciente al territorio

¿Podemos movernos por las aristas de un grafo comenzando en un

grafo exactamente una vez?

Un circuito euleriano en 𝖦 es un circuito que contiene a todas las aristas

Un recorrido euleriano en 𝖦 es un recorrido abierto que contiene a

𝖦 tiene un circuito euleriano, si y sólo si 𝖦=(Ⅴ, A) es conexo y todo

Se debe a los trabajos del matemático irlandés Sir Wiliam R. Hamilton

Prof.: Fernando Gerfauo Año 2019.-

Un ciclo hamiltoniano en 𝖦 es un ciclo de 𝖦 que contiene a cada uno de

Un camino hamiltoniano en 𝖦 es un camino simple (y no un ciclo) de 𝖦

Si bien existen teoremas que establecen condiciones necesarias o

particulares, se recurre frecuentemente al método de ensayo y error.

• Si 𝖦=(Ⅴ, A) tiene un ciclo hamiltoniano, entonces gr(v) 2, ∀v, v ∈ Ⅴ.

• Si a ∈ Ⅴ y gr(a)=2, entonces las dos aristas incidentes en el vértice a

• Si a ∈ Ⅴ y gr(a) >2, entonces cuando se trata de construir un ciclo

El químico inglés Arthur Cayley (1821-1895), investigando

El grafo 𝖦 es un árbol, si 𝖦 es conexo y no contiene ciclos.

Prof.: Fernando Gerfauo Año 2019.-

Un árbol recubridor de un grafo 𝖦 es un subgrafo recubridor de 𝖦 que

Prof.: Fernando Gerfauo Año 2019.-

Un árbol recubridor de un grafo 𝖦 es un subgrafo recubridor de 𝖦 que