GRAFOS

Grafos 

Es una estructura que posee elementos de una sola estructura relacionados con títulos de una misma base a estos elementos les llamaremos puntos y líneas.

El diagrama representativo de un grafo es una figura constituida por puntos unidos entre si, por segmentos o flechas.

Dirección: es ciertos grafos se indica la dirección de las líneas con una flecha. Los grafos en los que las líneas no tienen dirección se les denominan grafos no orientados.

Arista: líneas que conectan dos puntos en un grafo no orientado.

Arco: línea con dirección que conecta dos puntos en un grafo orientado.

Teoría de grafos:

Circuitos de Euler

Sea G un grafo sin vértices aislados un circuito que contiene todas las aristas de G recibe el nombre de circuito euleniano.

Teorema

Sea G un grafo, G contiene un circuito euleriano si solo si

·       G es conexo

·       Cada vértice de G es de grado par

    

                                        

Grado del vértices.

·       El grado de un vértice es el número de aristas que se encuentran en ese mismo vértice

·       Un circuito es una trayectoria que inicia y termina en el mismo vértice

·       Una gráfica es conexa si cualquiera de sus vértices se puede unir con una trayectoria.

·       Si una gráfica no es conexa se le denomina disconexa.

EJEMPLO:

·       A=2

·       B=2

·       C=3

·       D=3

·       E=1

·       F=3

·       G=2

·       H=2

·       I =2

CIRCUITO DE HAMILTON

Un ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G.

Empieza y termina en el mismo vértice y pasa por cada vértice una sola vez