Explorando Ciclos Eulerianos, Hamiltonianos y Grafos: Conceptos Clave
Clasificado en Matemáticas
Escrito el en 
español con un tamaño de 2,74 KB
Conceptos Fundamentales en Teoría de Grafos: Ciclos, Matrices y Más
Ciclo de Euler
El ciclo de Euler debe pasar por todas las aristas sin repetirse.
Ciclo Hamiltoniano
Debe pasar por todos los vértices sin repetir aristas o vértices.
Gráfica Bipartida Completa
Es K5,3; es decir, tiene 5 puntos V1 y 3 V2. Se une V1 con cada punto de V2 (aEv1 y dEv2).
Matriz de Adyacencia
Se colocan todos los vértices en fila y columna. Se irá comparando las aristas y se pondrá en la matriz el número de aristas que tocan un punto al otro.
Matriz de Incidencia
En la fila se pondrán las aristas y en la columna se pondrán los vértices. Se analizará si incide; si incide, se pondrá 1, y si no incide, se pondrá 0.
Tipos de Ciclos y Caminos
Ciclo Simple
(5,6,2,5) Inicia en 5 y termina en 5.
Camino Simple
(7)
Ciclo Simple (sin repetición de vértices)
(2,3,4,2) No se repite vértice.
Ciclo (con repetición de vértices)
(2,4,3,2,6,5,2) Se repite el vértice.
Isomorfismo de Grafos
#vértices y aristas tienen que ser iguales, grado de vértices iguales.
Ruta Más Corta
Se suma el valor de cada arista una por una, y la de menor valor se queda. Si se encuentra en suma paralela un número menor, se toma el más pequeño.
Gráfica Plana
(#aristas <=)
Ciclo de Euler
El ciclo de Euler debe pasar por todas las aristas sin repetirse.
Ciclo Hamiltoniano
Debe pasar por todos los vértices sin repetir aristas o vértices.
Gráfica Bipartida Completa
Es K5,3; es decir, tiene 5 puntos V1 y 3 V2. Se une V1 con cada punto de V2 (aEv1 y dEv2).
Matriz de Adyacencia
Se colocan todos los vértices en fila y columna. Se irá comparando las aristas y se pondrá en la matriz el número de aristas que tocan un punto al otro.
Matriz de Incidencia
En la fila se pondrán las aristas y en la columna se pondrán los vértices. Se analizará si incide; si incide, se pondrá 1, y si no incide, se pondrá 0.
Tipos de Ciclos y Caminos
Ciclo Simple
(5,6,2,5) Inicia en 5 y termina en 5.
Camino Simple
(7)
Ciclo Simple (sin repetición de vértices)
(2,3,4,2) No se repite vértice.
Ciclo (con repetición de vértices)
(2,4,3,2,6,5,2) Se repite el vértice.
Isomorfismo de Grafos
#vértices y aristas tienen que ser iguales, grado de vértices iguales.
Ruta Más Corta
Se suma el valor de cada arista una por una, y la de menor valor se queda. Si se encuentra en suma paralela un número menor, se toma el más pequeño.
Gráfica Plana
(#aristas <=)