UNIDAD 2. GRAFOS
Un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.
Un grafo simple está formado por dos conjuntos:
Un conjunto V de puntos llamados vértices o nodos.
Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados
TIPOS DE GRAFOS
Grafo simple entre dos nodos sólo hay un arco.
Multigrafo cuando tiene más de un arco.
Grafo Dirigido o Dígrafo Si los arcos se pueden recorrer en una en una dirección concreta pero no en la contraria y los arcos son entonces aristas.
Pseudografo si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante.
Leonhard Euler fué quien ideó los grafos como una manera muy potente y elegante de resolver el problema de los puentes de Königsberg
Las reglas estáticas (que sirven para dibujar un solo grafo y no una sucesión de ellos de forma dinámica) se dividen en :
Ejemplos: http://www.infovis.net/printMag.php?num=137&lang=1
Reglas básicas: se refieren a aspectos elementales como el solapamiento entre aristas vertices o ambos.
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 la información de sus etiquetas asociadas.
Reglas estructurales: son reglas de posicionamiento y enrutado relacionadas sólo con las propiedades de la teoría de grafos. Por ejemplo colocar los vértices de mayor orden en el centro del dibujo o minimizar la longitud total de aristas, minimizar el numero de cruces entre vértices, etc.