Yoyokiki

TRABAJO PRÁCTICO
GRAFOS
PÉREZ, Matias
Prof: Del RIO, Silvia

* ¿Qué es un GRAFO?
* ¿Cuáles son sus elementos?
* Definir grafos Eulerianos.
* Definir grafos Hamiltonianos.
*Hacer un ejemplo real de un grafo Eulerianos.
* Hacer un ejemplo real de un grafo Hamiltonianos.

* ¿Qué es un GRAFO?
Un grafo es una representación, un modelo, compuesto por un númerodeterminado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicarun camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo

* ¿Cuáles son sus elementos?
Un grafo (G) es un diagrama que consta de un conjunto de nodos(Vértices) y un conjunto de aristas (lados).

Nodos. Se indican por medio de un pequeño círculo y se le asigna un número o una letra.

Aristas. Son las líneas que unen un nodo con otro y se les asigna unaletra un número o una combinación de ambos.

Aristas paralelas. Son las aristas que tienen relación con un mismo par de nodos.

Lazo. Es aquella arista que sale de un nodo y regresa al mismonodo.

Valencia de un nodo. Es el número de aristas que salen o entran a un nodo.

* Definir grafos Eulerianos.
UN CAMINO EULERIANO es un camino que pasa por cada arista una y solo una vez. Unciclo o circuito Euleriano es un camino cerrado que recorre cada arista exactamente una vez. El problema de encontrar dichos caminos fue discutido por primera vez por Leonhard Euler, en elfamoso problema de los puentes de Königsberg.
UN CICLO O CIRCUITO EULERIANO es aquel camino que recorre todas las aristas de un grafo tan solo una única vez, siendo condición necesaria que regrese al vérticeinicial de salida. Se debe tener en cuenta que no importa la repetición de vértices mientras no se repitan aristas.
En la imagen (1,2,3,4,6,3,5,4,1) es un ciclo Euleriano, luego es un grafo Euleriano....