grafo

Matemáticas Discretas.
Relaciones.
CONALEP

Grafo
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo serepresenta gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones(las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Partes del grafo
Grafos.
Grafo.
Los grafos son representaciones de redes y por medio de ellos se pude expresar en forma visual y sencilla la relación entre elementos.
En computación los grafos se utilizan para mostrar las relaciones entre archivos en una base de datos, entre registros en una estructura de datos, entrecomputadoras en una red.

Partes de un grafo.
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 circulo y se le asigna un numero o una letra.

Aristas. Son las lineas que unen un nodo con otro y se les asigna una letra un numero o una combinación de ambos.

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

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

Valencia de un nodo. Es el numero de aristas que salen o entran a un nodo.

Tipos de grafos. 

Grafos simples. Son aquellos grafos que no tienen lazos ni aristas paralelas.

Grafo completo de orden N. Es el grafo en donde cada nodo esta relacionado con todos los demas, sinlazos ni lados paralelos. Se indica Kn en donde n es el numero de nodos. La valencia de cada uno de los nodos de los grafos completos esta dada por la expresión:
numero de aristas= n(n-1)/2
en donde n es el numero de nodos.

Grafo bipartito completo. Es el grafo que esta compuesto por dos conjuntos de nodos, uno de ellos A={a1, a2, a3, ....., an} y otro B={b1, b2, .....,bm} y en el que cada nodode A esta unido con todos los nodos de B, pero entre los nodos del mismo conjunto no existe ninguna arista que los una. Se indica como Kn,m en donde n y m es el numero de nodos de cada uno de los conjuntos.

Grafo dirigido. Es el grafo en donde las aristas tienen asociadas una dirección.


Complemento de un grafo. Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafocompleto de n vertices. Este grafo no tiene lazos ni ramas paralelas.

Caminos y circuitos
Caminos y circuitos.
Camino. 
Es una sucesión de lados que van de un nodo x a un nodo w (dichos lados se pueden repetir).

Circuito o ciclo.
Es un camino del nodo w al nodo w, esto es, un camino que regresa al mismo nodo de donde salió.


Circuito simple de longitud n.
Es aquel camino del nodo w alnodo w que solamente tiene un ciclo en la ruta que sigue.

Camino simple de longitud n.
Es una sucesión de lados que van de un nodo x a un nodo w, en donde los lados que componen dicho camino son distintos e iguales a n. Esto significa que no se puede pasar dos veces por una misma arista.

Camino de Euler. 
Es aquel camino que recorre todos los nodos pasando por todas las aristas solamenteuna vez. Una característica importante de los grafos que tienen camino de Euler es que siempre comienzan y terminan en nodos que terminan en valencia impar.

Circuito de Euler.
Es aquel ciclo que recorre todos los nodos pasando por todos las aristas solamente una vez.
Un grafo tiene un Circuito de Euler si y solo si es conexo y todos sus nodos tienen valencia par.

Algoritmo de Fleury....