TEORÍA DE GRAFOS

UNIVERSIDAD VERACRUZA

MATEMÁTICAS DISCRETAS

TEORÍA DE GRAFOS Y ALGORITMO SOBRE GRAFOS

1. ELEMENTOS Y CARACTERÍSTICAS DE LOS GRAFOS 

La teoría de grafos estudia las propiedades de los grafo (gráficas). El grafo es un conjunto de objetos llamados vértices (nodos) y una selección de pares de vértices, llamados aristas. El diagrama de Grafos se representa por una serie de vértices conectados a las aristas.

    1.1 COMPONENTES DE UN GRAFO (VÉRTICES, ARISTAS, LAZOS Y VALENCIA)

VÉRTICES

Son los nodos con los que se forman los grafos. Los grafos no dirigidos está formado por un conjunto de vértices y de aristas; y un grafo dirigido está formado 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 un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
• AISLADO: Es el vértice de grado Cero.
• TERMINAL: Vértice de grado 

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.

ARISTAS

La arista es la relación que tienen dos vértices de un grafo.

Las aristas se representan como una linea que une a dos vértices (esto es para grafos no dirigidos); si el grafo es dirigido, entonces la arista se representa como una flecha.

LAZOS 

Se denominan lazo cuando una arista conecta a un mismo vértice

VALENCIA

El grado o valencia de un vértice es el número de aristas incidentes en él. Para un grafo con bucles, éstos son contados por dos. En un dígrafo, podemos distinguir el grado saliente (el número de aristas que dejan el vértice) y el grado entrante (el número de aristas que entran en un vértice). El grado de un vértice sería la suma de ambos números.

     1.2 TIPOS DE GRAFOS

SIMPLE

Un grafo simple es un par G=(V;E) donde V es un conjunto_nito no vacío de elementos llamados vértices y E es un conjunto de pares no ordenados de elementos distintos de V llamados aristas. Por razones técnicas se supondrá que V\E=0

COMPLETOS

Un grafo completo es un grafo simple donde cada par de vértices está conectado por un arista.

BIPARTIDOS

Es un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro:

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

PLANOS

Un grafo es plano si, y sólo si, no contiene ningún subgrafo isomorfo a K5 ni a K3, 3, ni a subdivisiones de ellos. 

Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se intercepten. Los grafos K5 y El K3,3 son los grafos no planos minerales, lo cual nos permitirán caracterizar el resto de los grafos no planos. 

CONEXOS

En matemáticas y ciencias de la comunicación es aquel grafo que entre cualquier par de sus vértices existe un Camino (grafo) que los une.

PONDERADOS

Un grafo ponderado o grafo con pesos es un grafo G(V,E), en el que a cada arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas se introduce una función peso. El peso de un subgrafo ponderado es la suma de los pesos de todas las aristas.

2. ALGORITMOS DE RECORRIDO Y BÚSQUEDA

          2.1 EL CAMINO MÁS CORTO

El algoritmo de Dijkstra resuelve el problema de encontrar los caminos más cortos a partir de un origen, en grafos pesados que no tengan pesos negativos. El algoritmo de Dijkstra es un algoritmo voraz que opera a partir de un conjunto S de nodos cuya distancia más corta desde el origen ya es conocida. En principios, S contiene sólo el nodo origen. En cada paso, se agregan algún nodo V a S, cuya distancia desde el origen es la más corta posible. Bajo la hipótesis de que los pesos son no negativos, siempre es posible encontrar un camino más corto entre el origen y V que pasa sólo a través de los nodos de S, al que llamaremos "especial". 

        2.2 A LO ANCHO

Este algoritmo también se utiliza la estrategia de maracas los nodos como "visitados" para detectar la culminación del recorrido, pero los nodos se recorren de una manera ligeramente distinta. Este algoritmo puede crear menos ambientes recursivos que el anterior porque visita mas nodos en un mismo ambiente, pero esto depende de cómo este construido el grafo. El algoritmo se conoce como el algoritmo de BFS.

        2.3 EN PROFUNDIDAD

Para efectuar un recorrido en profundidad de un grafo, se selecciona cualquier nodo como punto de partida ( por lo general el primer nodo del grafo) y se marcan todos los nodos del grafo como "no visitados". El nodo inicial se marca como "visitado" y si hay un nodo adyacente a este que no haya sido "visitado", se toma este nodo como nuevo punto de partida del recorrido. El recorrido culmina cuando todos los nodos hayan sido visitados.

Jennifer Rivera Giles