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 de vértice

·       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.

CIRCUITO DE HAMILTON

Un circuito o ciclo hamiltoniano es un ciclo que contienen todos los vértices de g un circuito hamiltoniano es una trayectoria que empieza y termina en el mismo vértice y pasa por cada vértice una sola vez