Teoría de Grafos (parte 1)
Summary
TLDREn este video se introduce la teoría de grafos, comenzando con la definición de grafo como una estructura formada por vértices y aristas. Se explican conceptos clave como vértices adyacentes, aristas incidentes, aristas paralelas y bucles. Además, se enseña cómo representar grafos de manera gráfica y matricial, con ejemplos sobre la matriz de adyacencia y la matriz de incidencia. También se cubren los conceptos de grado de vértice, caminos, ciclos y condiciones para caminos y ciclos de Euler y Hamilton. Finalmente, se propone un ejercicio práctico para reforzar los conceptos.
Takeaways
- 📚 La teoría de grafos se define como una estructura formada por vértices, aristas y una función de incidencia.
- 🔵 Un grafo puede representarse mediante diagramas donde los vértices son puntos y las aristas son líneas que los conectan.
- 🔗 Los vértices son adyacentes si están conectados por al menos una arista.
- 🚫 Un vértice aislado no es adyacente a ningún otro vértice.
- ⚡ Las aristas adyacentes comparten un vértice en común, mientras que las aristas paralelas comparten los dos vértices.
- 🔄 Los bucles son aristas que conectan un vértice consigo mismo.
- 🔢 Un grafo simple no tiene aristas paralelas ni bucles.
- 🧮 Los grafos pueden representarse mediante matrices de adyacencia e incidencia, con valores booleanos que indican la presencia de conexiones.
- 📊 El grado o valencia de un vértice es el número de aristas que inciden en él, contando los bucles como doble.
- 🔄 Los caminos son sucesiones de aristas adyacentes, y los ciclos son caminos cerrados que vuelven al vértice inicial.
Q & A
¿Qué es un grafo según el script del vídeo?
-Un grafo es una estructura que se define como una terna formada por un conjunto de vértices, un conjunto de aristas y una función de incidencia que conecta aristas con vértices.
¿Cuál es la función de incidencia en un grafo?
-La función de incidencia es una relación que parte del conjunto de aristas y tiene como conjunto de llegada un conjunto de vértices, indicando los extremos de las aristas.
¿Cómo se representa gráficamente un grafo?
-En un grafo, los vértices se representan como puntos o circulitos y las aristas se dibujan como líneas que conectan los vértices. El orden de los vértices no importa, lo importante es cómo están conectados a través de las aristas.
¿Qué es un vértice adyacente en un grafo?
-Un vértice es adyacente a otro si existe al menos una arista que los une directamente.
¿Qué significa un vértice aislado en un grafo?
-Un vértice aislado es aquel que no está adyacente a ningún otro vértice, es decir, no está conectado a ningún otro vértice por ninguna arista.
¿Qué es una arista incidente en un vértice?
-Una arista es incidente en un vértice si el vértice es uno de los extremos de dicha arista.
¿Qué son las aristas adyacentes y cómo se definen?
-Las aristas adyacentes son aquellas que comparten un vértice en común. La intersección de sus conjuntos de vértices en cardinalidad es de 1.
¿Qué es un bucle en un grafo y cómo se define?
-Un bucle es una arista que tiene ambos extremos en el mismo vértice. Se define como una arista que, a través de la función de incidencia, tiene un cardinal de 1 en su imagen.
¿Qué es un grafo simple y qué características tiene?
-Un grafo simple es aquel que no contiene aristas paralelas ni bucles. Cada par de vértices está conectado por no más de una única arista y no hay aristas que se conecten un vértice consigo mismo.
¿Cómo se representan los grafos en forma matricial?
-Los grafos se representan en forma matricial a través de la matriz de adyacencia y la matriz de incidencia. La matriz de adyacencia es una matriz booleana que indica la adyacencia entre vértices, mientras que la matriz de incidencia indica la relación entre vértices y aristas.
¿Qué es el grado de un vértice en un grafo y cómo se calcula?
-El grado de un vértice es la cantidad de aristas que inciden en él. Si un vértice tiene un bucle, este se cuenta dos veces. Se calcula sumando el número de aristas incidentes a ese vértice.
¿Qué propiedad se cumple con los grados de los vértices de un grafo?
-La suma de los grados de todos los vértices de un grafo es igual al doble del número de aristas del grafo, ya que cada arista contribuye a aumentar en uno el grado de sus vértices extremos.
¿Qué es un camino en un grafo y cómo se define?
-Un camino en un grafo es una sucesión de aristas adyacentes que se siguen en secuencia. La longitud de un camino es el número de aristas que lo componen.
¿Qué es un ciclo en un grafo y cómo se diferencia de un camino?
-Un ciclo es un camino cerrado, es decir, comienza y termina en el mismo vértice. Para ser un ciclo, todas las aristas deben ser distintas excepto la primera y la última, que se repite.
¿Qué son los caminos de Euler y cuáles son las condiciones necesarias para que un grafo tenga uno?
-Los caminos de Euler son aquellos que pasan por cada arista del grafo exactamente una vez. Un grafo tiene un camino de Euler si y solo si es conexo y todos los vértices tienen grado par, o a lo sumo dos vértices tienen grado impar.
¿Qué es un ciclo de Hamilton y cuál es la diferencia con los caminos de Euler?
-Un ciclo de Hamilton es un ciclo que pasa por cada vértice del grafo exactamente una vez. La diferencia principal con los caminos de Euler es que en un ciclo de Hamilton, el grafo no necesita ser conexo y se enfoca en pasar por todos los vértices, no necesariamente por todas las aristas.
Outlines
📚 Introducción a la Teoría de Grafos
El primer párrafo introduce la teoría de grafos como una unidad de estudio en matemáticas. Se define un grafo como una terna que consiste en un conjunto de vértices, un conjunto de aristas y una función de incidencia. Se ilustra con un ejemplo donde se identifican los vértices y las aristas, y se explica cómo se representan gráficamente. Se menciona la flexibilidad en la disposición de los vértices en el diagrama, y se presentan definiciones adicionales como vértices adyacentes, aislados, aristas incidentes y bucles. También se establece la diferencia entre grafos simples y aquellos que contienen aristas paralelas o bucles.
📐 Matrices de Representación de Grafos
Este párrafo se enfoca en cómo representar grafos mediante matrices. Se explican las matrices de adyacencia y de incidencia, con ejemplos detallados para ilustrar cómo se llenan basándose en la presencia de aristas entre los vértices. Además, se introduce el concepto de grado de un vértice, que es el número de aristas incidentes a él, y se menciona la propiedad de que la suma de los grados de todos los vértices es igual al doble del número de aristas en el grafo.
🛤️ Caminos y Ciclos en Grafos
El tercer párrafo explora conceptos como caminos y ciclos dentro de los grafos. Se define un camino como una secuencia de aristas adyacentes y un ciclo como un camino cerrado que regresa al vértice inicial. Se diferencian los caminos simples, que no repiten vértices, de otros que pueden hacerlo. Se presentan ejemplos de caminos y ciclos, incluyendo ciclos simples y no simples, y se discuten las condiciones necesarias para la existencia de caminos de Euler y ciclos de Euler en un grafo, que requieren que todos los vértices tengan grado par.
🔍 Análisis de Grafos y Ejercicios
Este segmento se centra en el análisis de grafos, donde se examina si un grafo es simple, se construye su matriz de adyacencia y se calcula el grado de sus vértices. Se busca un camino de Euler y un ciclo de Euler si corresponde, así como un ciclo de Hamilton, que pasa por todos los vértices exactamente una vez. Se propone un ejercicio práctico para aplicar estos conceptos, analizando un grafo dado y buscando los caminos y ciclos mencionados. El vídeo concluye con una invitación a continuar el aprendizaje en la siguiente parte.
👋 Despedida y Proceso de Aprendizaje
El último párrafo es una despedida del presentador, quien resalta la importancia de la teoría de grafos y anima a los espectadores a aplicar lo aprendido. Se sugiere que los espectadores han adquirido una base sólida para continuar explorando la materia en el siguiente vídeo, dejando expectación por más contenido educativo.
Mindmap
Keywords
💡Teoría de grafos
💡Grafo
💡Vértices
💡Aristas
💡Función de incidencia
💡Matriz de adyacencia
💡Grado de un vértice
💡Camino
💡Ciclo
💡Camino de Euler
💡Ciclo de Hamilton
Highlights
Definición de un grafo como una terna formada por un conjunto de vértices, un conjunto de aristas y una función de incidencia.
Ejemplo gráfico de un grafo con vértices y aristas, mostrando la función de incidencia.
Observación sobre la libertad en la disposición de los vértices en un grafo.
Definición de vértices adyacentes basada en la existencia de aristas que los unan.
Identificación de un vértice aislado que no es adyacente a ningún otro vértice.
Explicación de qué es una arista incidente en un vértice y ejemplos en el grafo.
Definición de aristas adyacentes y paralelas en términos de su función de incidencia.
Introducción a los bucles o lazos como aristas con ambos extremos en el mismo vértice.
Definición de un grafo simple que no contiene aristas paralelas ni bucles.
Representación de grafos mediante matrices: matriz de adyacencia y matriz de incidencia.
Ejemplo práctico de cómo construir una matriz de adyacencia para un grafo dado.
Construcción de una matriz de incidencia, diferenciando entre aristas y vértices.
Explicación del grado o valencia de un vértice y su importancia en grafos.
Propiedad fundamental de los grados de los vértices: la suma de los grados es dos veces el número de aristas.
Ejercicio resuelto para determinar la cantidad total de vértices en un grafo dado grados y aristas.
Definición y ejemplos de caminos y ciclos en grafos.
Explicación de la longitud de caminos y ciclos y cómo se determina.
Introducción a los caminos y ciclos eulerianos, con condiciones para su existencia en grafos.
Descripción de los caminos y ciclos hamiltonianos y su importancia en la teoría de grafos.
Ejercicio propuesto para aplicar conceptos de grafos, incluyendo la búsqueda de caminos eulerianos y hamiltonianos.
Transcripts
bienvenidos a este vídeo en el cual
vamos a comenzar a estudiar una unidad
muy interesante de nuestra materia que
es la teoría de grafos
bueno vamos a comenzar con las
definiciones que es un grafo un grafo se
puede definir como una estructura que es
una terna formada por un conjunto de
vértices que no debe ser vacío un
conjunto de aristas y una función de
incidencia que parte del conjunto de
aristas y tiene como conjunto de llegada
ave entre paréntesis lo que significa
esto es un conjunto que puede estar
formado por uno o dos elementos debe y
ellos van a ser los extremos de las
aristas
vamos a entender lo más fácil mirando
este ejemplo supongamos que nos dan este
grafo el conjunto de vértices tiene
desde 1 hasta b 5 y aristas desde a1
hasta 5 y la función de incidencia acá
vino expresada que pide a 1 v1 v2 idea
12 es de 3 ven en este caso hay uno solo
un solo vértice en las restantes hay dos
que significa esto mejor es graficar lo
si como es que lo podemos diagramar los
vértices van a ser todos los dibujamos
como puntitos sino circulitos y ahora
nos fijamos la arista a uno
la función de incidencia que tenía cuál
era y la arista a1 si nos fijamos acá
dice que pide a uno es de un 92 por lo
tanto vamos a dibujar una arista entre a
b1 y b2 y ésta se llama a1
pero qué pasa con la arista a 2 ésta es
la que tenía un solo vértice entonces
bbv 3 b 3 es una arista
que empieza y termina en el mismo
vértice bueno y así seguimos dibujando
la arista 3 está entre debe estar entre
b 4 y b2 la arista 4 tiene que estar
entre 1 y b 3
y la arista 5 entre 1 y 2 que ya había
una o sea que ahora hay dos si este es
el diagrama del grafo es mucho más fácil
verlo gráficamente
[Música]
una observación importante nosotros
dibujamos el grafo así pusimos los
vértices en cualquier disposición porque
porque no hay ninguna regla que nos diga
cómo ubicarlos o sea que por ejemplo el
mismo grafo anterior yo lo podría haber
dibujado de esta manera lo importante es
como estamos vinculando a los vértices
si se fijan las aristas están ubicadas
entre los vértices que correspondían
pero como vemos el diagrama distinto al
vértice 5 está allá arriba sí así que lo
importante es cómo vinculamos a los
vértices a través de las aristas por eso
no hay un único diagrama
vamos a ver ahora un montón de
definiciones pero son muy sencillas
vamos a ir a empezar vértices anders
hacen test dice la definición que un
vértice ve su vía es adyacente vj si
existe alguna arista tal que la fide
dicha arista sean estos dos vértices
dicho de otra manera que significa
significa que el dos vértices son
adyacentes cuando están unidos por al
menos una arista en el ejemplo que
estábamos viendo antes quienes serían
los vértices adyacentes al b2
quienes están unidos con b2 b1 y ve 4
exactamente de 24 tiene una arista que
los une y con b 1 tiene dos aristas pero
bueno existe es al menos una bien vamos
a otra definición
que será un vértice aislado el que no es
adyacente a ningún otro si en este caso
por supuesto es cual el de 5
otra definición que serán las aristas
incidentes en un vértice dice la
definición que una arista es incidente
un vértice si el vértice pertenece a fi
de dicha lista qué significa esto que
las que tienen a dicha ha dicho vértice
por extremo no entonces por ejemplo aquí
las aristas a 1 a 3 y a 5 son los
incidentes en el vértice 2 porque son
las que tienen el vértice 2 como uno de
sus extremos
que serán aristas adyacentes dice que la
que la intersección de las fi de dichas
aristas en módulo perdón en cardinal
tiene que ser 1 a ver esto qué significa
que son las que tienen un único vértice
en común si por ejemplo a uno ya tres
son adyacentes ya que el único vértice
en común que tienen es de dos
en cambio que son las aristas paralelas
y las que tienen la misma función de
incidencia o sea ahora comparten los dos
vértices quienes son paralelas en este
caso a 1 y a 5
que serán los bucles o lazos dice que
son aquellos que piden las son las
aristas que su imagen a través de fin es
de cardinal 1
entonces en este caso cuál sería la que
están
con ambos extremos en el mismo vértice a
2 en este ejemplo es a 2 un bucle
la definición de grafos simple dice que
es el que no tiene aristas paralelas ni
bucles este que estábamos viendo por
supuesto no es simple porque hay las dos
cosas justamente hay aristas paralelas y
además bucle en cambio este otro que les
pongo acá abajo si es simple cumple la
definición
bueno los grafos se van a representar en
forma matricial para eso vamos a nombrar
a los vértices como b1 hasta adn y a las
aristas a 1 hasta a m porque puede ser
distinta cantidad con esto vamos a
definir dos matrices una que se llama
matriz de adyacencia y otra que se llama
matriz de incidencia veamos la primera
la matriz de adyacencia pide que
sea una matriz booleana cuadrada de n
por n es decir la cantidad de vértices y
cada elemento m psuv y j va a poder
valer como son booleana valen 120 cuando
vale 1 cuando el vértice debe subir es
adyacente al bj y 0 cuando no lo sea
entonces vamos a ver un ejemplo
aquí tenemos este grafo tenemos 5
vértices es decir que la matriz de
presencia va a ser de 5 x 5 los vamos a
ubicar en este orden creciente 1 2 3 4 y
5 y entonces cuando nos fijemos el
vértice 1 por ejemplo con cuál es
adyacente el vértice 1 si vemos es
adyacente con el 2
con el 4 y con el 5 entonces en la fila
del vértice 1 vamos a poner unos en esos
tres lugares
luego el vértice 2 con quien es
adyacente el vértice 2 es con el 1 que
ya lo habíamos marcado con el 3 y con el
4 si por eso es que van apareciendo ahí
los unos en la matriz
la de incidencia es una matriz fíjense
no necesariamente cuadrada porque es de
n por m las filas van a representar los
vértices y las columnas van a
representar las aristas y los elementos
también pueden valer unos y ceros en qué
caso uno cuando el vértice sea extremo
de la arista y cero si no lo es en este
caso entonces
vamos a ver en el ejemplo
en este caso teníamos 5 vértices y las
aristas son 8 la matriz va a ser de 5 x
8 nos conviene llenarla en forma
vertical como es eso bueno ponemos los
cinco vértices y ahora digo la arista a
uno vamos a comenzar con esta fíjense
acá está entre que vértices está entre
el 1 y el 2
entonces va a ir 11 porque ponemos en
orden a los vértices 000 cuando
escribamos la arista a 2 donde va a
tener 12 esta arista va a tener unos
entre el 1 y el 5 sí y así con todas
vean la arista 1 tenía 11 y todos ceros
la arista 2 le estamos viendo si esta es
la 1
esta es la 2 esta es la 3 y así hasta
llegar a la octava que la octava ésta
/
el 3 y el 5
vamos a definir ahora lo que es el grado
o valencia de cada vértice es una
función justamente que se le aplica a
los vértices y nos devuelve la cantidad
de aristas que inciden si fuera un bucle
se cuenta doble por ejemplo se acuerdan
de este grafo que habíamos trabajado
hace un ratito cuál es el grado del
vértice 1 me tengo que fijar cuántas
aristas son incidentes al vértice unos y
entonces yo veo que acá sale una acá
sale otra y acá sale otra quiere decir
que el grado de este vértice es 3
el del b2 también 1 2 y 3 sí
él debe 4 por ejemplo que va a ser uno
solo ven que hay una sola vez 5 que va a
ser cero ib3 que va a ser una que llega
de acá y el bucle ven que están los dos
extremos por eso el bucle se cuenta
doblemente vamos a escribir entonces
logrado que se pone g de cada uno gdv
uno debe 2 ahí tenemos todos los grados
de este ejemplo
hay una propiedad que se cumple con los
grados de los vértices dice que si yo
sumo todos los grados eso siempre me da
el doble de la cantidad de aristas que
en símbolo lo podemos poner así porque
es cierto y porque cada arista aporta en
sus dos extremos aporta un grado un
vértice y otro a otro si es una arista
que no es bucle o bien aportados al
grado del mismo vértice por eso están
contadas dos veces
en el ejemplo que teníamos nosotros se
acuerdan que recién habíamos calculado
los vértices si yo sumo todo esto que me
da 9 más 110 que justamente fíjense es
el doble de las aristas porque éste
tenía 5 aristas
vamos a resolver este ejercicio si a
nosotros nos dicen cuál es la cantidad
total de vértices de un grafo que tiene
dos vértices de grado cuatro uno de
grado tres cinco de grado dos y el resto
colgante colgante significa de grado uno
sabiendo que en total hay doce aristas
para resolver este ejercicio nos viene
bien la propiedad anterior no es cierto
sumemos todos los grados de los vértices
si había dos de grado cuatro dos por
cuatro más uno por tres más 5 x 2 más x
cantidad que no sabemos de grado uno
tiene que ser igual a dos por 12 que es
la cantidad de aristas
que nos quedó acá una ecuación lineal en
una sola incógnita o sea que de aquí
vamos a poder despejar x x es 3 pero x
era la cantidad como puse ahí de
vértices colgantes no es la cantidad
total de vértices cuál sería la cantidad
total de vértices había dos de grado 4
así que hay 21 de 35 de 2 más estos x
esta sería la cantidad de vértices que
nos da 11 una posibilidad de un grafo
que cumpla con esto es esta que acá les
dibujo pero no es la única pueden pensar
otras
vamos a ver ahora qué son los caminos y
los ciclos un camino dice la definición
es una sucesión de aristas adyacentes un
ciclo es cuando tenemos un camino
cerrado es decir que volvemos al vértice
inicial
la longitud en camino es la cantidad de
aristas que lo forman y un camino se
llama simple cuando todos los vértices
son distintos
vamos a ver un ejemplo acá me dan este
gráfico que tiene siete vértices y
también tiene varias aristas vamos a
nombrar algunos caminos posibles desde
el vértice 1 hasta el vértice 6 sin
indicar la longitud de cada
bueno un posible camino podría ser este
ven a
efe como lo nombramos se puede ir
poniendo vértice arista vértice arista
y en este caso qué longitud tiene
cuántas aristas utilizo 3 por eso la
longitud es 3
es un camino simple repitió algún
vértice no nos repitió entonces es
simple
pero no es el único
por ejemplo otro camino podría ser
pasando por el 4 utilizando el bucle si
este que marque como lo escribimos este
camino 2 1 y 4 jota otra vez 4 etcétera
qué longitud tiene éste tiene longitud 5
y es simple fíjense que incluso como
está escrito el camino se nota bien que
está repetido cual vértice el 4 por eso
no es simple
a ver otro podría ser un ciclo que les
parece este
ven que este es un camino cerrado vamos
a escribirlo empezó en el vértice 1 y
terminó nuevamente en el 1 la longitud
es 4 este es un ciclo y es un ciclo
simple si en este caso es simple no está
utilizando el bucle meant
vamos a ver otro ciclo que les parece
este
se escriben 356 f3 la longitud de estrés
y este también es simple si este simple
tratemos de buscar uno que no sea simple
a ver qué les parece este no
necesariamente tiene que usar bucles
fíjense que este ciclo ahí está escrito
tiene longitud 7 empezó y terminó en el
vértice 1 y qué pasa
este que repite repite el vértice 3 por
eso no es simple sí
hay algunos caminos y ciclos especiales
que se llaman eulària nos que son los
caminos de euler los que pasan por todas
las aristas sólo una vez y ciclo es
que cumple lo mismo pero siendo simple o
no
grafo tiene camino bulería no si sólo si
es con exo y todos los vértices tienen
grado par oa lo sumo dos tienen grado
impar esta es una condición necesaria y
suficiente y para que tenga ciclo blair
ya no si o si todos los vértices deben
tener grado par a qué se debe esto a que
cada vez que pasamos por un vértice
estamos entrando con un grado y saliendo
con otro si estamos utilizando dos
grados si el vértice lo volvemos a pasar
otra vez utilizamos cuatro si lo
volvemos a pasar seis por eso es que
todos los grados deben ser pares
por ejemplo miremos es telégrafo
cuál es el grado de cada vértice este de
acá arriba tiene grado 2
este 1234 este 1234
pero estos dos de abajo tienen grado 3 y
este grado 3 los dos de abajo sí por lo
tanto como hay dos vértices de grado
impar qué ocurre
no hay ciclo de euler pero si camino y
se debe empezar y terminar justamente en
los de grado impar vamos a verlo
empecemos ahí después sigo por acá por
acá por ejemplo ahí sigo con esta ha
sido con esta y ahí terminé mi recorrido
en todas las aristas uno puede pensarlo
como un jueguito de dibujar el grafo sin
levantar el lápiz y acá se pudo hacer
pero con esa limitación que empecé y
terminé en distinto vértice y tenían que
ser justamente los de grado impar
en cambio en este otro ejemplo revisemos
todos los grados como son todos los
grados son pares aquí porque este
vértice tiene grado 2
4 este otro 4
este otro 2 este 4 y este otro 4 todos
tienen grado para entonces acá si va a
haber un ciclo de euler se animan a
encontrarlo
hay otro tipo de caminos y ciclos que se
llaman hamiltonianos que es un camino de
hamilton el que pasa por todos los
vértices una sola vez sí porque pide
simple y ciclo en el caso que se ha
cerrado por supuesto
si bien aquí hay algunas condiciones
suficientes que no se las voy a nombrar
no hay condiciones aún que sean
necesarias y suficientes sí pero en
general es más fácil encontrar caminos
de hamilton si no necesariamente tiene
que pasar por todas las aristas
este tipo de camino no hay que confundir
con los dedos vamos a ver un ejemplo
miren este grafo que el indio
tendrá camino de hamilton hay que pasar
por todos los vértices una única vez por
cada uno y dijimos no hace falta pasar
por todas las aristas así que un posible
ciclo de hamilton es este que acá les
muestro ave de
efe
y vuelve a utilizo sólo esas aristas
en este mismo grafo ustedes podrían
analizar luego también si hay un nuevo
camino de euler ahí si tenemos
condiciones que todos tengan grado par
que creo que en este caso se cumple
pueden después investigarlo
y aquí vamos a terminar esta primera
parte de la unidad con un ejercicio
propuesto para ustedes dado el siguiente
gráfico que aquí está primero van a
tener que analizar si es simple escribir
la matriz de adyacencia van a indicar el
grado de cada vértice hallar un camino
de euler si existe o ciclo y también un
ciclo de hamilton y así con esto más o
menos repasan un poquito lo que vimos en
este vídeo
y luego vamos a continuar en la parte 2
los espero en el próximo vídeo espero
que les haya servido hasta luego
5.0 / 5 (0 votes)