Matematicas Discretas

TEORIA DE GRAFOS

Conceptos básicos de grafos
Definiremos un grafo como un sistema matemático abstracto. Sin embargo para poder ofrecer una motivación de la terminología utilizada y para desarrollar cierto conocimiento intuitivo, representaremos los grafos como diagramas.
Los grafos son la representación natural de las redes, en las que estamos cada vez más incluidos. Exploramos quéson los grafos, para qué sirven y algunas reglas para dibujarlos bien.
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:
• Un conjunto V de puntos llamados vértices o nodos.

• Un conjunto de pares de vérticesque se llaman aristas o arcos y que indican qué nodos están relacionados.
De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.
En un grafo simple entre dos nodos sólo hay un arco. Si hay más de un arco hablamos de un multigrafo. Si los arcos se pueden recorrer en una dirección concreta pero no en lacontraria lo llamamos grafo dirigido o dígrafo y los arcos son entonces aristas, si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante se llama pseudografo. 
A pesar de que un grafo parece una estructura muy elemental, hay muchísimas propiedades de los grafos cuyo estudio ha dado lugar a una completa teoría matemática.
Ejemplos de grafos que todos conocemos sonlos organigramas que explicitan la estructura formal de la empresa, los árboles genealógicos o la circuitería de los chips electrónicos. Se usan regularmente para resolver problemas en la eficiencia del transporte, en sociología, electrónica y electricidad, detección de fraude y en general en aquellos campos en los que la conectividad es importante.
De hecho vivimos en una sociedadinterconectada en la que, por definición, las redes (que son simplemente una forma de grafos dirigidos en los que cada arco tiene un valor) forman cada vez más parte de nuestra experiencia diaria. No es fácil representar apropiadamente un grafo.
Ejemplos: carreteras, diagramas de flujo, de tuberías, de plomería, curricula de una carrera, cableados, trayectos de viajes, etc.
Reglas básicas: serefieren a aspectos elementales como el solapamiento entre aristas vértices o ambos.
|Reglas Básicas |
|[pic] |[| |[|[pic] |
| |p||p| |
| |i| |i| |
| |c| |c| |
| |]||]| |


Reglas semánticas: son reglas de posicionamiento de vértices y de dibujo de arcos o aristas (enrutado) derivadas del significado de vértices y aristas. Por ejemplo dibujar el tamaño de un vértice o el grosor de una arista en función de su importancia. Suelen venir dadas por el usuario o son deducidas de lainformación de sus etiquetas asociadas.
|Reglas Semánticas |
|[pic] |[| |[|[pic] |
| |p| |p|...