Teoría de Grafos (parte 1)

Summary

En 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

00:00

📚 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.

05:00

📐 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.

10:01

🛤️ 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.

15:06

🔍 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.

20:07

👋 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.

Keywords

💡Teoría de grafos

La teoría de grafos es una rama de las matemáticas discretas que estudia las propiedades y estructuras de los grafos, que son conjuntos de vértices conectados por aristas. En el video, esta teoría es el tema central, ya que se exploran sus conceptos básicos y aplicaciones en la modelación de sistemas y la resolución de problemas.

💡Grafo

Un grafo es una estructura formada por un conjunto de vértices, un conjunto de aristas y una función de incidencia que relaciona vértices y aristas. En el video, se define y se usa como base para introducir conceptos más complejos, como la matriz de adyacencia y los grados de los vértices.

💡Vértices

Los vértices son los puntos básicos de un grafo, a los cuales se les puede asociar características como el grado, que es el número de aristas que conectan con otros vértices. En el video, los vértices se representan gráficamente como puntos y son fundamentales para entender la estructura del grafo.

💡Aristas

Las aristas son las conexiones que unen dos vértices en un grafo. Pueden ser simples o múltiples, y su presencia define la forma en que los vértices están interconectados. En el video, se discuten las características de las aristas y cómo se representan en las matrices asociadas al grafo.

💡Función de incidencia

La función de incidencia es una relación que asocia cada arista de un grafo con uno o dos vértices, que son sus extremos. Esta función es crucial para definir la estructura del grafo y se usa para construir las matrices de adyacencia y de incidencia.

💡Matriz de adyacencia

La matriz de adyacencia es una representación matemática de un grafo, donde cada elemento indica si hay una arista que une dos vértices específicos. En el video, se explica cómo construir esta matriz a partir de la información del grafo y se usa para ilustrar cómo se modela la relación entre vértices.

💡Grado de un vértice

El grado de un vértice es el número de aristas que inciden en él. Es una medida de la conectividad de un vértice dentro del grafo. En el video, se calcula el grado de los vértices para entender mejor la topología del grafo y para resolver problemas relacionados con la estructura del grafo.

💡Camino

Un camino en un grafo es una secuencia de vértices donde cada par de vértices consecutivos están conectados por una arista. Los caminos son fundamentales en la teoría de grafos para estudiar la conectividad y el flujo dentro de los grafos. En el video, se exploran los caminos y sus propiedades, como la longitud y la simplicidad.

💡Ciclo

Un ciclo es un tipo especial de camino que comienza y termina en el mismo vértice, y donde todos los vértices son distintos, excepto el primero y el último. Los ciclos son importantes en la teoría de grafos porque pueden indicar la existencia de bucles o la capacidad de recorrer el grafo de manera contínua. En el video, se analizan los ciclos y se discuten sus características, como ser simple o no.

💡Camino de Euler

Un camino de Euler es un camino que recorre cada arista del grafo exactamente una vez. Es una de las estructuras más buscadas en la teoría de grafos, ya que implica una conectividad óptima. En el video, se menciona cómo identificar si un grafo tiene un camino de Euler y se relaciona con la paridad del grado de los vértices.

💡Ciclo de Hamilton

Un ciclo de Hamilton es un ciclo que pasa por cada vértice del grafo exactamente una vez, excepto el vértice de inicio/fin, que se repite. Es una estructura de grafos que tiene aplicaciones en problemas de optimización y rutas. En el video, se explora la existencia de ciclos de Hamilton y se relaciona con la complejidad de encontrar tales ciclos en grafos arbitrarios.

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