grafos

1. UTILIDADES DE LOS GRAFOS EN INGENIERÍA INFORMÁTICA
Como herramienta informática para la construcción, edición y análisis que pueden ser de
utilidad para la resolución de problemas, también, para otras disciplinas relacionadas como la
investigación operativa, diseño de redes, ingeniería de organización industrial, la logística y el
transporte entre otras. Un grafo puede representar en formade red un modelo de una
realidad empresarial. Este modelo podrá ser analizado desde distintos puntos de vista
gracias a los algoritmos en los que pueden ser implementados los grafos. En informática, se
puede usar sin restricciones.
Los grafos pueden ser utilizados en el desarrollo de diversas aplicaciones informáticas, como
en el control de un sistema de vía aérea o terrestre, entre muchasotras.

2. GRAFOS, DEFINICIONES
 Vértices o Nodos: Son los nodos con los que se forman los grafos. Los grafos no dirigidos
se forman por un conjunto de vértices y aristas; y un grafo dirigido esta compuesto por un
conjunto de vértices y arcos(pares ordenados de vértices).
Se dice que un vértice es:
Adyacente: si tenemos un par de vértices de un grafo (U,V), y si tenemos una arista que losune, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el
adyacente.
Aislado: es el vértice de grado cero.
Terminal: vértice de grado uno.
Un vértice de corte es aquel que al removerlo desconecta al grafo restante. Un conjunto
independiente es un conjunto de vértices tal que ninguno es adyacente a otro, y una
cobertura de vértices es un conjunto de vértices queincluye los puntos finales de cada arista
en un grafo.
 Aristas: Las aristas es la relación que tienen dos vértices de un grafo.
Las aristas se representan como una línea que une dos vértices (esto es para grafos no
dirigidos); si el grao es dirigido, entonces la arista se representa como una flecha.
 Valencia: El grado o valencia de un vértice es el número de aristas incidentes en él.Para
un grafo con bucles, estos son conectados por dos. En un dígrafo, podemos distinguir el
grado saliente (el numero de aristas que dejan el vértice). El grado del vértice seria la
suma de ambos números.


Camino: es una sucesión finita en la que aparecen alternadamente vértices y aristas de
dicho grafo

 Bucles: es una arista que relaciona al mismo nodo, es decir, una arista donde elnodo
inicial y el nodo final coinciden.
 Circuito: es un camino en el que coinciden los vértices inicial y final. Un circuito se

dice simple cuando todos los arcos que lo forman son distintos y se dice elemental cuando
todos los vértices por los que pasa son distintos.

3. MULTIGRAFOS
Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es
decir,aristas que relacionan los mismos nodos. De esta forma, dos nodos pueden estar
conectados por más de una arista. Formalmente, un multigrafo G es un par G:=(V, E) donde:
 V es un conjunto de vértices o nodos
 E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas.

Un multigrafo con múltiples aristas (en rojo) y tres bucles (en azul). No todos los autores
permitenmultigrafos con bucles.
4. CLASES DE GRAFOS
 Grafos simples o No Dirigido: Un grafo es simple si a lo más existe una arista uniendo dos
vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única
que une dos vértices específicos. Un grafo que no es simple se denomina multigrafo.
 Grafo completo: Un grafo es completo si existen aristas uniendo todos los pares posiblesde vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El
conjunto de los grafos completos es denominado usualmente K, siendo Kn el grafo
completo de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente
n(n-1)/2
aristas.
La representación gráfica de los como los vértices de un polígono regular da cuenta de su
peculiar estructura....