Ingeniero

Páginas: 15 (3665 palabras) Publicado: 26 de octubre de 2012
MATEMATICA DISCRETA MAT-151

UNIDAD DIDACTICA III TEORIA DE GRAFICAS AUTOR: MIGUEL ANGEL SANCHEZ ALMONTE

1

5

2

4

3

SANT O DOMINGO, D. N. MAYO, 2004 1

UNIDAD III
Teoría de Gráficas

3.1 Gráfica El concepto de gráfica es abstracto, aunque una gráfica puede representar una situación de objetos reales. Es el caso de la representación de la relación entre los componentes queconforman una red de computadoras, una red eléctrica, una red de antenas de transmisión de radiofrecuencias entre otras.

Concepto de gráfica: Podemos tener la idea de una gráfica como la representación geométrica que consta de un conjunto finito de objetos (V) llamados vértices, un conjunto finito de objetos (E) llamados aristas, y una función () que asigna a cada arista los extremos en dichagráfica.

Además, podemos definir una gráfica G como un par (V, E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de V x V (conjunto de aristas).

Gráficamente representaremos los vértices por puntos y las aristas por líneas que los unen. Un vértice puede ser extremo de cero, uno, dos o más aristas, pero toda arista debe unir exactamente 2 vértices.

Llamaremosorden de un grafo a su número de vértices, |V|. Si |V| es finito se dice que el grafo es finito. Es bueno hacer hincapié en el sentido de que en esta asignatura estudiaremos los grafos finitos, centrándonos sobre todo en esta unidad en los grafos no dirigidos.

De aquí en adelante, utilizaremos como notación de una gráfica G, la expresión: G = (V, E, )

;

Donde:

V es el conjunto devértices de la gráfica, E es el conjunto de aristas y,  es la función que define los extremos de cada aristas.
2

A continuación te presentaré un ejemplo de una gráfica dada de la siguiente forma:

Ejemplo: Si tenemos la gráfica G definida por los siguientes datos, dibujar la imagen que la representa.

V = { 1, 2, 3, 4, 5, 6, 7}, E = {e1, e2, e3, e4, e5, e6, e7, e8, e9 }, (e1)= {1, 3}, (e2)=(e3)= {2, 4}, (e4)= {1, 5}, (e5)={3, 6}, (e6)={6, 7}, (e7)={2, 7}, (e8)= {4, 6}, (e9)= {5, 6}. Lo primero que debemos hacer es representar los vértices en cualquier posición y luego, unir estos vértices, tomando en cuenta los extremos de cada una de las aristas dadas. Así se obtiene la siguiente imagen. 1 2

7

3

6 5 Fig. 1

4

Es bueno aclarar que la imagen de una gráfica no esúnica, ya que dependerá de las diferentes posiciones en que hayamos colocado los vértices. Lo que importa es, que cualquier imagen de una gráfica dada, siempre tendrá una sola interpretación.

A continuación te presentaré una imagen de la gráfica anterior, sin embargo, ambas imágenes son diferentes. 1 5 2 3 6 7 Fig. 2 4

3

Como puedes notar, las componentes de las gráficas son los vértices ylas aristas. Ahora explicaremos de forma concreta en lo que consiste cada uno. 3.1.1 Aristas y Vértices

La forma gráfica que utilizaremos para representar los vértices será a través de puntos y las aristas por líneas que los unen.

Si tenemos una arista cuyos extremos son a y b, y esta carece de dirección, entones se puede denotar indistintamente {a, b} o {b, a}, siendo a y b los vértices queune. De ahí que si {a, b} es una arista, a los vértices a y b se les llama sus extremos.

Definición: El grado de un vértice está determinado por el número de aristas que tienen como extremo a ese vértice.

Puede ocurrir en una gráfica, que una arista inicie y termine en el mismo vértice y en este caso el grado del vértice aumenta en dos.

Observando la gráfica del ejemplo anterior, podemosobservar que:

El grado del vértice 1 es 2 El grado del vértice 2 es 3 El grado del vértice 6 es 4

Definición: Vértice aislado es aquel vértice que no es extremo de ninguna arista en una gráfica dada.

Una característica que tienen los vértices aislados es que su grado siempre será cero.

4

Veamos a continuación dos ejemplos donde se presentan casos gráficas con vértices...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Ingeniero
  • Ingeniero
  • Ingeniero
  • Ingeniero
  • Ingeniero
  • Ingeniero
  • Ingeniero
  • Ingeniero

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS