CLASE 5 UNIDAD 2 GRAFOS

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.