Investigación de Grafos

[pic 1][pic 2]

[pic 3][pic 4]

 [pic 5][pic 6][pic 7][pic 8]

GRAFOS[pic 9]

Un grafo esta formado por un conjunto de nodos o vértices y un conjunto de arcos cada arco cada arco en un grafo se especifica por un par de nodos.

Los grafos resultan ser extremadamente útiles para analizar problemas diversos, por ejemplo: Asignación de tarea, Construcción de redes y problemas de horarios                        

TERMINOLOGIA

Orden del grafo: Es el número de nodos que contiene el grafo        

Nodos Adyacentes: Son así si dos nodos contienen un arco que los une.

Incidencia: Es cuando una arista o vértice es incidencia si está unida a otro.

Nodos Múltiples: Son múltiples o paralelos si inciden sobre los mismos vértices

Lazo: Es una arista cuyos extremos inciden sobre el mismo vértice.

Camino: Es una secuencia de uno o mas arcos que conectan dos nodos.

Conectado: Se denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario

Longitud: Al numero de aristas del camino.

Ciclo: Es el camino de un nodo así mismo

Grado de Vértice: Es el numero de aristas incidentes a él.

CLASIFICACIÓN

Grafo directo o dígrafo : Son solo si los pares de nodos tienen los arcos dirigidos

Grafo no dirigido: Son cuando las aristas no están orientadas

Grafo Completo: Cuando cada nodo esta conectado con todos y cada uno de los nodos restantes

Grafo Regular: Cuándo cada vértice tiene el mismo grado.

Grafo Simple: Es aquel que no pose lazos ni aristas paralelas.

Multi Grafo: Esta facultado para tener aristas múltiples es decir aristas que relacionan los mismos nodos.

Grafo Bipartito: Es un grafo cuyo conjunto de vértices puede ser particionado en dos clases que tal forma que los 2 vértices de la misma clase no sean jamás adyacentes.

Grafos isomorfos: Debe tener el mismo de vértices y aristas

...