A√ļn no tienes acceso a esta clase

Crea una cuenta y contin√ļa viendo este curso

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 56

Preguntas 2

Ordenar por:

¬ŅQuieres ver m√°s aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesi√≥n.

Principio de redes neuronales. S√ļper emocionado por esto.

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

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?

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

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.

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.

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)

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.

El teorema que menciona el profe:

Saludos !

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

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?

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.

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.

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?

Teniendo en cuenta que el ejemplo utilizado en realidad es un contraejemplo (contradice lo ense√Īado). ¬ŅComo ser√≠a el teorema de verdad?

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.