Grados, caminos, cadenas y ciclos

La ecuación que nos dice que la suma de todos los grados de los vertices es igual a dos veces el número de aristas se llama "Lema del apretón de manos"
De hecho, es muy intuitivo de demostrar. Dado que una arista existe cuando se unen dos vertices y existe una sola arista por cada dos vertices, si uno tiene n aristas entonces obtendrá 2n grado de vertices. UwU

Principio de redes neuronales. Súper emocionado por esto.

me recuerda el famoso problema de los puentes de Koninsberg que el mega genio de Euler resolvio y abrió el camino a la topologia

MINUTO 4:25 como trollear a tus amigos con matemáticas jajaj

Los nodos son los vértices y los caminos son las aristas ¿Cierto?

El teorema que menciona el profe:

Saludos !

Grado de un nodo:
Es el número de aristas o conexiones que tiene un nodo. Se representa con δ()
Nota
La sumatoria de los grados de los vertices es igual al doble del número de aristas:
Σδ(v) = 2(E)

Caminos, Cadenas y Ciclos:

• Cadena: Sucesión de aristas y conexiones que recorren un grafo
• Camino: Cadena que no puede repetir ninguna arista o conexión.
• Ciclo: Camino que inicia y termina en un punto (el único que se repite)
• Cadena cerrada: Cadena que inicia y termina en un punto (se puede repetir aristas y vertices)

Grafo Conexo:
Grafo en el que todos los vertices están conectados entre sí (hay un camino que conecta ambos vértices)

Si es psoble visitar todos los vertices, pero se dejarian fuera varios caminos.

Teorema de Euler:
a. Si un grafo conexo tiene más de dos nodos con grado impar, no existe un camino simple de Euler.

b. Si existen exactamente dos vértices de grado impar, el grafo se puede recorrer, pero el camino ha de empezar en uno de los dos vértices de grado impar y terminar en el otro.

c. Si no existen vértices de grado impar, el grafo se puede recorrer. El camino siempre será cerrado.

Corríjanme si me equivoco.

• Si se puede hacer es recorrer todo los NODOS sin repetir ARISTAS (caminos)
• No se puede hacer recorrer todas las ARISTAS sin repetir NODOS.

Mencionaste un truco de que si más de dos vértices tienen un grado impar, entonces no se puede recorrer todas las aristas sin pasar dos veces por una. Este truco solo funciona para figuras cerradas no?

Una cadena cerrada es una combinacion entre una cadena y un camino porque se repiten los nodos y tenemos que llegar al mismo nodo de donde comenzamos.

pues yo lo hice pero no asi como en el video? eso significa que no seta bien, mi resolución ?

Teniendo en cuenta que el ejemplo utilizado en realidad es un contraejemplo (contradice lo enseñado). ¿Como sería el teorema de verdad?

Algo interesante es que: Como sabemos que la sumatoria de los grados de “v” es igual al doble de las aristas, esto implica que la sumatoria de los grados de “v” dividido 2 es igual al número de aristas, claro, esto sirve siempre y cuando puedas contar todas las aristas de un grafo, pero a medida que se agregan más nodos el contar cuantas aristas hay se vuelve complicado, entonces:

Supongamos v nodos de un grafo simple, sabiendo que el grado de un nodo es igual al número de aristas a las que esta conectado, es lógico deducir que
el grado de un vertice es igual a todos los demás vertices excepto el mismo, osea

grado(v) = v - 1 sabiendo esto podemos decir que cada nodo pose v - 1 aristas(e)
esto implica que (v-1)v es igual a la sumatoria de los grados de v
entonces esto significa que vv - v = 2e entonces (v*v-v)/2 = e

Asi se sabria el numero de aristas que posee un grafo dependiendo solamente del numero de nodos de este.

ACLARACIÓN: claro que el grado de nodo no siempre es v-1, ya que este puede no estar conectado con todos los demás nodos, solo con algunos, de igual manera se pueden establecer los grados que uno quiera y retocar la formula acorde a ello y esta seguiria funcionando.

No esta clara la explicacion de por que no se puede recorrer el grafo.
En el video dice …" trata de recorrer todos los vertices mediante un camino…" y si se puede, segun las siguientes definiciones:
Cadena: a toda sucesion finita y alterna de vertices y aristas
Camino: a toda cadena en la que no se repiten ni vertices ni aristas

Se entiende perfecto, no sé porque dicen algunos que faltó explicar, repitan el video, lo entenderán.

Bastante buena esta clase.

Esos me recuerdan a una charla corta que Sergio dio en el canal de YouTube de Platzi

Yo en mi vida he visto algo así (soy del área de la salud y no estudiamos esto) y me sorprende lo fácil que hace ver todos estos temas

Mis apuntes

https://www.remnote.io/a/grados-caminos-cadenas-y-ciclos/6390eedb19eda1e1600c7bfe

Hay varios tipos de graficas.

Si los vertices son pares, se pueden visitar los caminos
En cambio, si tenemos vertices con un grado impar, es imposible hallar un camino que recorra todos los vertices.

Caminos, cadenas y ciclos
Cadena: sucessión de vertices, conexiones.
Camino: no se pueden repetir recorridos aqui.
Ciclo: el unico vertice que se repite es el final.
Cadena cerrada: iniciar en un nodo, terminar en un nodo y se pueden repetir los vertices en los que se ha pasado.
No Conexo

Cómo se llama el teorema que nos indica que si tenemos más de dos vértices con grado impar es imposible recorrer de una sola vez todo el grafo sin repetir un camino?

grafo conexo es donde estan todos los vertices conectado entre si

cadena cerrado repito node y puedo reprtirlos

un ciclo es donde solo se puede repetir el unico vertice que es el final

camino son sucesiones donde no se puede repetir ni nungun verticeas ni nungun node

cadena es un sucesion de aristas y de acciones

si un grafo tiene mas de 2 vertices con grado impar no se puede recorrer todos los nodos sin repetir alguno

la sumatorias de todos los grados de mi vertices es igual a 2 veces por el numero de aristas que tenemos en nuestro grafo

Jugados que pueden ser retados para amigos

Los grafos son conexos, cuando tienen todos los nodos conectados entre sí. Cuando no, los llamamos No conexos.

Existe la cadena cerrada, en la que podemos hacer un camino más felxible, ya que podemos repetir vértices y caminos, pero teenemos que comenzar y terminar en el mismo nodo.

Un ciclo es un camino, en el que podemos repetir un solo vértice o nodo, pero este tiene que ser el nodo de inicio, es decir que empieza y termina en el mismo vértice.

Un camino es un recorrido entre el grafo, en el que no puedo repetir ningún vértice ni ninguna conexción.

Una cadena es una sucesión de aristas y conexiones, con los cuales yo puedo recorrer mi gráfico. Una serie que no tiene que tener mucho sentido.

Los grafos que tienen más de dos nodos con conexiones impares, son imposibles de recorrer todos los caminos, sin repetir al menos uno.

Una prueba muy interesante de los grafos, es recorrelos, sin subir el lapiz. La regla es que no podemos repetir caminos, pero tenemos que recorrerlo todo.

La sumatoria de todos las conexiones, es igual a 2 veces las aristas.

La arista es el número de aristas que tiene un nodo.

Ahora estoy viendo de donde sacaban los ejercicios mis profes de la universidad jeje.

3:16 Y yo intentado durante 15 minutos encontrar el camino JAJAJA

• El grado de cada nodo en el grafo, es el número de enlaces que tiene a otros nodos

• Propiedad: la suma del grado de todos los nodos en un grado es igual a la suma de todos sus enlaces por dos

• Teorema: si un grafo tiene más de dos nodos con grado impar, no se puede recorrer todo el grafo sin pasar dos veces por él mismo enlace

• Cadena, cadena cerrada, camino, ciclo, conexo, no conexo

Genial!!!

Para definir los grafos tenemos en cuenta si al ir de un nodo a otro lo hacemos una vez, mas de una vez o ninguna vez. Además, cuántas veces se pasa de un vertice a otro.

El reto de recorrer todos los caminos sin repetir me recordó a este otro juego. Se trata de pasar por todos los espacios y cruzar todas las líneas sin pasar dos veces por la misma línea.

Se entiende perfecto.

Se entiende perfectamente!

Repetí varias veces este capítulo para tener buenos apuntes (con dibujos y todo) jaja

Tengo la misma inquietud de la cadena y cadena cerrada, diferencia?

Como se llama el teorema mencionado?

En un ciclo es necesario contar con todos los nodos o podemos dejar algunos afuera y hacer el ciclo?

Cuál es diferencia entre cadena y cadena cerrada ?

Uppsss…yo me concentre en que vértice son los nodos o puntos. Pero eran lados. Me equivoque…Ayuda!!!

Muy buena clase.