No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Grados, caminos, cadenas y ciclos

18/40
Recursos

驴Qu茅 es el grado de un v茅rtice?
Es el n煤mero de aristas que tiene un nodo con otros nodos.

  • Existe una propiedad matem谩tica que nos dice que la sumatoria de todos los grados de los v茅rtices de un grafo es igual al doble de las aristas.
  • Otra propiedad 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.
  • Una cadena es una sucesi贸n de v茅rtices y de conexiones entre s铆.
  • Un camino a diferencia de una cadena es una sucesi贸n de v茅rtices y conexiones donde no puedes repetir ning煤n v茅rtice ni conexi贸n, mientras en un ciclo el v茅rtice de inicio es igual al v茅rtice donde termina.
  • Un grafo conexo es aquel donde todos los nodos est谩n unidos entre s铆.

Aportes 61

Preguntas 2

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

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 鈥渧鈥 es igual al doble de las aristas, esto implica que la sumatoria de los grados de 鈥渧鈥 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

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鈥o me concentre en que v茅rtice son los nodos o puntos. Pero eran lados. Me equivoque鈥yuda!!!

Muy buena clase.