grafos

Universidad Tecnológica de Panamá
Facultad de Ingeniera de Sistemas Computacionales
Departamento de Computación y Simulación de Sistemas
ESTRUCTURA DE DATOS II
Prof.: Ing. Henry J. Lezcano- MAS
con Postgrado en Docencia Superior

GRAFOS
Los Grafos tienen aplicaciones en diversos campos como lo son:






La Sociología
La Química
La Geografía
Ingeniería Eléctrica
Ingeniería Industrial, etcCon los arboles se han representados relaciones entre objetos en la que existe
una solo jerarquía. Con frecuencia, es necesario representar relaciones
arbitrarias entre objetos de datos, es decir un grafo.
Ing. Henry J. Lezcano FISC-UTP-2014

1

Clasificación de los Grafos
En grafos dirigidos y grafos no dirigidos los cuales representan modelos de
relaciones arbitrarias .

Grafo NO Dirigido

GrafoDirigido

LOS GRAFOS SON USADOS PARA REPRESENTAR:
• Redes de Alcantarillados
• Redes de Comunicación
• Circuitos Eléctricos, Etc.

Estudio de un problema mediantes grafos:
Primero representar el caso en estudio mediante el grado.
• En esta representación cada elemento o cada objeto del problema representa un
nodo.
• La relación, comunicación o conexión entre los nodos da lugar a una arista, quepuede ser dirigida o bidireccional(no dirigida).
Una ves modelado el problema mediante grafos se puede hacer un estudio de sus
diversas propiedades. Esta teoría ha sido aplicada en diversas ciencias.
Ing. Henry J. Lezcano FISC-UTP-2014

2

Para el estudio de un Red de Comunicaciones
Impresora
Modem

PC1

Servidor

PC2

Grafo Representativo

Ing. Henry J. Lezcano FISC-UTP-2014

3

Conceptos yDefiniciones de Grafos
Un grafo consiste en un conjunto de vértices o nodos ‘V’ y un conjunto de arcos o
aristas ‘A’. Y se representas por G = {V, A}

4

1

Conjunto de Aristas A={(1,4),(4,1), (1,5),
(5,1), (7,5), (5,7),……..}

5
7

Conjunto de Vértices V={1,4,5,7,9}

9

Forman el Grafo No dirigido G={V,A}

MODELO 1

Ing. Henry J. Lezcano FISC-UTP-2014

4

Conceptos y Definiciones de Grafos
Un grafoconsiste en un conjunto de vértices o nodos ‘V’ y un conjunto de arcos o
aristas ‘A’. Y se representas por G = {V, A}

Conjunto de Vértices V={C, D, R, F, H}

E

C

Conjunto de Aristas A={(C,D),(D,F), (E,C), (E,H),
(H,E)}

F
D

H

Forman el Grafo dirigido G={V,A}

MODELO 2

Ing. Henry J. Lezcano FISC-UTP-2014

5

Conceptos, características y propiedades de los Grafos
 Un arco o arista estaformado por un par de nodos y se escribe ( u, v) siendo u, v
los nodos correspondientes en el grafo.
 Un grafo es dirigido si los pares de nodos que forman los arcos o aristas son
ordenados y serán representados por u  v.
 Un grafo no dirigido es aquel en que los arcos o aristas están formados por pares
de nodos no ordenados o no apuntados y serán representados por u --- v.
 Bucle: a un arco se lellama bucle si tiene los extremos idénticos.
 Grado de entrada de un vértice: representan el numero de arcos que terminan en
un determinado nodo y se identifica por ge (vi).
 Grado de salida de un vértice: representan el numero de arcos que inician en un
determinado nodo y se identifica por gs (vi).
 Camino: secuencia de arcos de forma tal que el vértice final de cada uno sirve de
vérticeinicial al siguiente. Y se representa por P = ( V 0, V1, V2, …..Vn)
Ing. Henry J. Lezcano FISC-UTP-2014

6

Conceptos, características y propiedades de los Grafos
 Camino Simple: un camino es simple si todos lo nodos que forma el camino son
distintos, pudiendo ser iguales los extremos del camino
4

7

P = (4, 6, 9, 7)
Es un camino de longitud = 3

10

6

9

11

 Circuito o Ciclo: es un camino cerradoen la cual el vértice inicial coincide con el
vértice final.
A

B

C

P = (A,E,B,F,A)
Es un camino de longitud = 4
D

E

F
Ing. Henry J. Lezcano FISC-UTP-2014

7

Conceptos, características y propiedades de los Grafos
 Grafo Conexo: un grafo es conexo si cada par de vértices está conectado por un
camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino
posible...