UNIVERSIDAD NACIONAL DE TRUJILLO
Facultad de Ciencias agropecuarias
ESCUELA DE AGRONOMIA

TEORIA DE GRAFOS

MONOGRAFÍA

Por:
Rojas Max Juan Francisco

Trujillo – 2014
Curso de Matemática Básica

ÍNDICE

Resumen………………………………………………………………………. 1

Introducción........................................................................................... 2

I. Grafos - Conceptos fundamentales…………………………….……… 3

1. Aristas
2. Vértices
3. Caminos
II. Representación de grafos………………………………………………… 5

1. Estructura de lista
2. Estructuras matriciales
III. Tipos y caracterización de grafos…………………………………….. 7

1. Grafos dirigidos
2. Multigrafos
3. Grafos conexos
4. Grafos completos
5. Grafos bipartitos
6. …ver más…

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. Se aprecia mejor según la siguiente imagen

Fig. 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.
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.
Vértices
Son los puntos o nodos con los que está 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