Los grafos

REPÚBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA LA DEFENSA

UNIVERSIDAD NACIONAL EXPERIMENTAL POLITÉCNICA

DE LA FUERZA ARMADA BOLIVARIANA

NÚCLEO ANZOÁTEGUI – SAN TOMÉ

CÁTEDRA: Ing. De Sistemas

GRAFOS

Facilitador: Bachilleres: Prof. Ing. Robert Andrade Alland J Scioville C.I: 12.681.840

Sección: 5-N01

Ing. De Sistemas

San Tomé, Diciembre de 2012.

INTRODUCCION

Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.

En este trabajo se tratará brevemente de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación en algún programa informático, así como en la memoria.

En este trabajo, traté de ser lo más breve posible explicando de manera muy sencilla los conceptos y algunas metodologías con un lenguaje no tan rebuscado para su mayor entendimiento.

Dada esta pequeña introducción empezará el desarrollo del tema

GRAFOS

Definiciones

Un grafo G es un par G=(V, E) donde V es un conjunto finito de elementos llamados vértices o nodos y E un conjunto de pares no ordenados de vértices que se denominan aristas o arcos.

Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc.

La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.

Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

Propiedades

1. El número de vértices de un grafo G, es el orden del grafo.

2. El número de aristas de un grafo G, es su tamaño.

3. Dos aristas son independientes si no tienen vértices en común.

4. Si una arista relaciona dos vértices (u,v) se dicen que u y v son vértices adyacentes.

5. Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Ejemplo:

Para el siguiente grafo, determine el número de vértices y aristas; escriba además, dos vértices adyacentes y dos independientes.

Grafo con 5 vértices y 8 aristas

Número de vértices = 5

Número de aristas = 8

Los vértices u y v son vértices adyacentes.

Los vértices u y w son vértices independientes.

Vértices

Son los puntos o nodos con los que esta conformado un grafo.

Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es par o impar según lo sea su grado.

• Vértices Adyacentes: 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.

• Vértice Aislado: Es un vértice de grado cero.

• Vértice Terminal: Es un vértice de grado 1.

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a, b} es una arista, a los vértices a y b se les llama sus extremos.

Gráficamente las aristas se representan, para el caso de los grafos no dirigidos, como una línea que une a los dos vértices. Si el grafo es dirigido, entonces la arista se representa como una flecha, que parte del nodo origen y apunta al nodo destino.

No es obligatorio que todo vértice esté unido con otro por una arista. Tales vértices se llaman vértices o nodos aislados.

Tampoco es necesario que ambos nodos unidos por una arista sean distintos. Dado un vértice a, de existir una arista {a, a} o bien (a, a), entonces decimos que el grafo posee un bucle.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.

• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

• Cruce: Son dos aristas que cruzan en un punto.

Grado de un grafo.

• Grado de incidencia positivo: El grado de incidencia positivo de un nodonjes el número de arcos que tienen como nodo inicial anj. Ejemplo: El grado de incidencia de 1 es igual a 3.

• Grado de incidencia negativo: El grado de incidencia negativo de un nodonjes el número de arcos que terminan ennj. Ejemplo: El grado de incidencia negativo de 1 es igual a 1.

• Grado de un nodo: Paradigrafoses el grado de incidencia positivo menos el grado de incidencia negativo del nodo. Ejemplo: El grado de 1 es igual a 3 –1 = 2, el grado del nodo 4 es 2 –2 = 0. Para grafos no dirigidos es el número de líneas asociadas al nodo.

Grado de un vértice en un grafo

Se denomina grado de un vértice v de un grafo no dirigido G al número de aristas que inciden en v, y se designará g(v) (un lazo en v contribuye de manera doble al grado de v).

Grado de un vértice en un dígrafo

En un grafo dirigido, el grado de salida es el número de aristas que salen de él, y el grado de entrada es el número

...