Chacón Zamora José Christian
González García Andrea
Vázquez Gutiérrez Favio
DEFINICION
 Es la representación gráfica de los datos de una
situación en particular.
 Es un conjunto, no vacío, de objetos llamados vértices
o nodos y una selección de pares de vértices, llamados
aristas esto se representa mediante una serie de
puntos conectados por líneas.
 Son estructuras de datos no lineales que tienen una
naturaleza generalmente dinámica.
Grafo Regular: Cada vértice tiene el mismo grado o
valencia.
Grafo bipartito: Cuyos vértices se pueden separar en
dos conjuntos disjuntos y las aristas siempre unen
vértices de un conjunto con vértices de otro.
Grafo completo: Cada par de vértices está conectado
por una arista.
*Grafo Nulo: Los vértices que lo componen
no están conectados, son vértices aislados.
*Grafo
Isomorfos:
Existe
una
correspondencia biunívoca (uno a uno), entre
sus vértices de tal forma que dos de estos
quedan unidos por una arista en común.
*Grafos Platónicos: Formados por los
vértices y aristas de los cinco sólidos
regulares, a saber, el tetraedro, el cubo, el
octaedro, el dodecaedro y el icosaedro.
*Grafos Conexos: Si cualquier
vértice V pertenece al conjunto de
vértices y es alcanzable por algún
otro. No dirigido de modo que
para cualquier par de nodos existe
al menos un camino que los une.
GRAFO DIRIGIDO: Es un conjunto de pares ordenados de
elementos.
Se representa como una flecha, que
parte del nodo origen y apunta al nodo destino.
GRAFO NO DIRIGIDO: Es un conjunto
de pares no ordenados de elementos.
Es una línea que une a los dos vértices.
Los grafos se representan en memoria secuencial
mediante matrices de adyacencia. Una matriz de
adyacencia, es una matriz de dimensión n*n, en
donde n es el número de vértices que almacena
valores booleanos, donde matriz M[i, j] es verdadero
si y solo si existe un arco que vaya del vértice y al
vértice j.
La Matriz de adyacencia que se obtuvo a
partir del grafo anterior es la siguiente:
Los grafos se representan en memoria enlazada
mediante listas de adyacencia. Una lista de
adyacencia, se define de la siguiente manera: Para un
vértice i es una lista en cierto orden formada por todos
los vértices adyacentes [a, i]. Se puede representar un
grafo por medio de un arreglo donde cabeza de i es
una puntador a la lista de adyacencia al vértice i.
La lista de adyacencia, que se obtuvo a
partir del grafo anterior es la siguiente:
CIRCUITO DE HAMILTON
En un grafo se tiene un circuito de Hamilton cuando se
inicie en un nodo y termina en el mismo pasando
exactamente una vez por cada nodo.
CIRCUITO DE VENN EULER
Este circuito se da en grafos donde se
realiza un camino donde se puede pasar
solo una vez por cada arco.
El factor de peso o Ponderación se da en un
grafo en el cual hay datos asociados con un arco.
Circuitos y Caminos De Euler.
Un circuito Euleriano en un grafo
G es un circuito simple que contiene cada
arista de G.
Un camino Euleriano en G es un camino simple
que contiene
cada arista en G.
Pases y Circuitos de Hamilton.
Un paseo hamiltoniano es un paseo que pasa a
través de cada un de los vértices exactamente
una vez.
Un circuito hamiltoniano como un paseo circuito
que pasa a través de cada un de los vértices
exactamente una vez.