Diferencia entre revisiones de «Grafo euleriano»

(Fuentes.)
m (Texto reemplazado: «<div align="justify">» por «»)
(No se muestra una edición intermedia de otro usuario)
Línea 1: Línea 1:
 
{{Definición|nombre=Grafo euleriano|imagen=k23.png|concepto=[[Grafo]] compuesto por un [[ciclo euleriano]].}}
 
{{Definición|nombre=Grafo euleriano|imagen=k23.png|concepto=[[Grafo]] compuesto por un [[ciclo euleriano]].}}
<div align="justify">
+
 
'''Grafo euleriano'''. Dícese de los grafos no orientados formados por un ciclo euleriano; es decir, aquellos que pueden recorrerse completamente desde un vértice y regresar al punto de origen sin pasar dos veces por la misma [[arista]].
+
'''Grafo euleriano'''. Dícese de los grafos no orientados formados por un ciclo euleriano; es decir, aquellos que pueden recorrerse completamente desde un vértice y regresar al punto de origen sin pasar dos veces por la misma arista.
  
 
El nombre de este tipo de grafos proviene del matemático [[Leonard Euler]] quien abordó por primera vez el asunto de cómo debían caracterizarse los grafos para poder recorrerse de la manera deseada tras desestimar el [[problema de los puentes de Königsberg]].
 
El nombre de este tipo de grafos proviene del matemático [[Leonard Euler]] quien abordó por primera vez el asunto de cómo debían caracterizarse los grafos para poder recorrerse de la manera deseada tras desestimar el [[problema de los puentes de Königsberg]].

Revisión del 22:23 21 ago 2019

Grafo euleriano
Información sobre la plantilla
K23.png
Concepto:Grafo compuesto por un ciclo euleriano.

Grafo euleriano. Dícese de los grafos no orientados formados por un ciclo euleriano; es decir, aquellos que pueden recorrerse completamente desde un vértice y regresar al punto de origen sin pasar dos veces por la misma arista.

El nombre de este tipo de grafos proviene del matemático Leonard Euler quien abordó por primera vez el asunto de cómo debían caracterizarse los grafos para poder recorrerse de la manera deseada tras desestimar el problema de los puentes de Königsberg.

El problema análogo de recorrido pero que en lugar de limitar el doble paso por las aristas lo hace impidiendo que se transite dos veces por los vértices ha dado lugar a la existencia de los grafos hamiltonianos.

Antecendentes.

El problema de los 7 puentes de la ciudad de Königsberg (hoy Kaliningrado) constituyó durante mucho tiempo un rompecabezas para personas comunes y entendidos en matemáticas y aunque existía la sospecha de que fuese insoluble tampoco había una forma de decir definitivamente que no tuviera solución.

No fue hasta que Euler caracterizó el problema y la forma que habían de tener los grafos que pudieran satisfacerlo en 1736, que finalmente quedó probado que el famoso problema carecía de solución. De esta forma, también comenzaba a existir la teoría de grafos. Con el análisis de los grafos eulerianos se formularon además las condiciones para saber si el camino euleriano era abierto o cerrado (cíclico), llegando a una versión completa de la caracterización de los grafos en 1873 de la mano de Carl Hierholzer.

Definiciones.

Casos particulares.

Un grafo G=<V,A> no dirigido y conexo que tiene exactamente 2 vértices de grado impar, entonces tiene un camino euleriano no cerrado.

Un grafo G=<V,A> no dirigido y conexo cuyos vértices tienen grado par, entonces tiene un ciclo euleriano.

Teorema general.

Sea un grafo G=<V,A> no dirigido y conexo, entonces las expresiones siguientes equivalen:

  1. G es grafo euleriano.
  2. Todos sus vertices tienen grado par no nulo.

Propiedades.

  • Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
  • Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
  • Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
  • Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
  • Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: traversable) si es conexo y al menos dos vértices en el grafo tienen grado impar.

Veáse también.

Fuentes.

  1. K. Ribnikov. Análisis Combinatorio. Editorial Mir. Moscú, 1988. Páginas 17-23.
  2. Grafo euleriano en Wikipedia. Consultado el 1 de junio de 2012.