teoria_de_graficas
Páginas: 63 (15595 palabras)
Publicado: 24 de septiembre de 2015
TEORIA DE GRAFICAS
INTRODUCCIÓN
La teoría de gráficas o teoría de grafos es aplicada en una gran cantidad de áreas tales como
ciencias sociales, lingüística, ciencias físicas, ingeniería de comunicación, y otras. La teoría
de grafos también juega un papel importante en varias áreas de la ciencia de la computación,
tales como teoría de cambio y lógica de diseño, inteligencia artificial, lenguajesformales,
gráficos por computadora, sistemas operativos, compiladores, y organización y recuperación
de información.
CONCEPTOS BÁSICOS DE LA TEORIA DE GRAFOS
La terminología usada en la teoría de grafos no es estándar. No es poco usual encontrar que
varios términos diferentes son usados como sinónimos. Esta situación, de cualquier manera,
llega a ser más complicada cuando descubrimos que untérmino en particular es usado por
diferentes autores para referirse a conceptos desiguales. Esta situación es natural debido a
la gran diversidad de campos en los que la teoría de gráficas se aplica.
En esta sección debemos definir un grafo como un sistema matemático abstracto. De
cualquier manera, para dar algo de sentido a la terminología usada y también para
desarrollar algunas ideas intuitivas, serepresentará un grafo por medio de un diagrama. Ese
diagrama se llamará igualmente grafo. Las definiciones y términos aquí presentados no están
restringidos a aquellos grafos que pueden ser representados por medio de diagramas,
aunque parezca ser el caso ya que estos términos tengan una fuerte asociación con dicha
representación. Debemos resaltar que una representación diagramática es posibleúnicamente en casos muy simples. Los métodos alternativos para representar grafos serán
igualmente discutidos.
Definiciones básicas
Primeramente se consideraran varios grafos que son presentados por medio de diagramas.
Algunos de estos grafos pueden ser considerados como grafos de cierta relación, pero hay
algunos otros que no pueden ser interpretados de esta manera.
Considérese el diagrama de lafigura 1.1. Para el propósito de nuestro estudio, estos
diagramas representarán grafos. Nótese que cada diagrama consiste de un conjunto de
elementos que son representados por puntos o círculos y están en ocasiones etiquetados
como v1, v2,..., o 1,2,.... También, en cada diagrama ciertas parejas de dichos puntos están
conectados por líneas o arcos.
Definición. Un grafo G = V , E ,ϕ consiste de unconjunto V no vació llamado el conjunto de
nodos (puntos, vértices) del grafo, donde E es el conjunto de los ejes del grafo, y φ es un
mapeo del conjunto de ejes E a un conjunto ordenado o desordenado de elementos pares de
V.
Debemos asumir de lo anterior que ambos, los conjuntos V y E de un grafo son finitos. Sería
conveniente denotar un grafo G como V , E , o simplemente como G. Nótese que ladefinición
de grafo implica que para cada eje del grafo G podemos asociar una pareja ordenada o no
ordenada de nodos pertenecientes al grafo. Si un eje x ∈ E está asociado con un par
ordenado (u, v) o un par no ordenado (u, v), donde u, v ∈ V , entonces se dice que el eje x
conecta o une los nodos u y v. Cualquier par de nodos que estén conectados por un eje en
un grafo son llamados nodos adyacentes.Definición. En un grafo G = (V,E), un eje que esté asociado a un par ordenado de V x V es
llamado eje dirigido de G, mientras un eje que esté asociado a un par no ordenado de
nodos es llamado eje no dirigido. Un grafo del cual cada nodo es dirigido es llamado
dígrafo o grafo dirigido. Un grafo en el cual cada eje es no dirigido es llamado grafo no
dirigido. Si algunos ejes son dirigidos y otros nodirigidos en un grafo, se trata de un grafo
mixto.
v1
v2
v1
v2
v1
v2
Fig.1 Los grafos (b), (e) y (g) son grafos dirigidos. Los grafos mostrados en (c) y (f) son no dirigidos.
El grafo (e) es mixto. El grafo de (a) puede considerarse como dirigido y no dirigido.
El mapa de una ciudad que muestra solamente un sentido de las calles es un ejemplo de
grafo dirigido en el que losa nodos son...
INTRODUCCIÓN
La teoría de gráficas o teoría de grafos es aplicada en una gran cantidad de áreas tales como
ciencias sociales, lingüística, ciencias físicas, ingeniería de comunicación, y otras. La teoría
de grafos también juega un papel importante en varias áreas de la ciencia de la computación,
tales como teoría de cambio y lógica de diseño, inteligencia artificial, lenguajesformales,
gráficos por computadora, sistemas operativos, compiladores, y organización y recuperación
de información.
CONCEPTOS BÁSICOS DE LA TEORIA DE GRAFOS
La terminología usada en la teoría de grafos no es estándar. No es poco usual encontrar que
varios términos diferentes son usados como sinónimos. Esta situación, de cualquier manera,
llega a ser más complicada cuando descubrimos que untérmino en particular es usado por
diferentes autores para referirse a conceptos desiguales. Esta situación es natural debido a
la gran diversidad de campos en los que la teoría de gráficas se aplica.
En esta sección debemos definir un grafo como un sistema matemático abstracto. De
cualquier manera, para dar algo de sentido a la terminología usada y también para
desarrollar algunas ideas intuitivas, serepresentará un grafo por medio de un diagrama. Ese
diagrama se llamará igualmente grafo. Las definiciones y términos aquí presentados no están
restringidos a aquellos grafos que pueden ser representados por medio de diagramas,
aunque parezca ser el caso ya que estos términos tengan una fuerte asociación con dicha
representación. Debemos resaltar que una representación diagramática es posibleúnicamente en casos muy simples. Los métodos alternativos para representar grafos serán
igualmente discutidos.
Definiciones básicas
Primeramente se consideraran varios grafos que son presentados por medio de diagramas.
Algunos de estos grafos pueden ser considerados como grafos de cierta relación, pero hay
algunos otros que no pueden ser interpretados de esta manera.
Considérese el diagrama de lafigura 1.1. Para el propósito de nuestro estudio, estos
diagramas representarán grafos. Nótese que cada diagrama consiste de un conjunto de
elementos que son representados por puntos o círculos y están en ocasiones etiquetados
como v1, v2,..., o 1,2,.... También, en cada diagrama ciertas parejas de dichos puntos están
conectados por líneas o arcos.
Definición. Un grafo G = V , E ,ϕ consiste de unconjunto V no vació llamado el conjunto de
nodos (puntos, vértices) del grafo, donde E es el conjunto de los ejes del grafo, y φ es un
mapeo del conjunto de ejes E a un conjunto ordenado o desordenado de elementos pares de
V.
Debemos asumir de lo anterior que ambos, los conjuntos V y E de un grafo son finitos. Sería
conveniente denotar un grafo G como V , E , o simplemente como G. Nótese que ladefinición
de grafo implica que para cada eje del grafo G podemos asociar una pareja ordenada o no
ordenada de nodos pertenecientes al grafo. Si un eje x ∈ E está asociado con un par
ordenado (u, v) o un par no ordenado (u, v), donde u, v ∈ V , entonces se dice que el eje x
conecta o une los nodos u y v. Cualquier par de nodos que estén conectados por un eje en
un grafo son llamados nodos adyacentes.Definición. En un grafo G = (V,E), un eje que esté asociado a un par ordenado de V x V es
llamado eje dirigido de G, mientras un eje que esté asociado a un par no ordenado de
nodos es llamado eje no dirigido. Un grafo del cual cada nodo es dirigido es llamado
dígrafo o grafo dirigido. Un grafo en el cual cada eje es no dirigido es llamado grafo no
dirigido. Si algunos ejes son dirigidos y otros nodirigidos en un grafo, se trata de un grafo
mixto.
v1
v2
v1
v2
v1
v2
Fig.1 Los grafos (b), (e) y (g) son grafos dirigidos. Los grafos mostrados en (c) y (f) son no dirigidos.
El grafo (e) es mixto. El grafo de (a) puede considerarse como dirigido y no dirigido.
El mapa de una ciudad que muestra solamente un sentido de las calles es un ejemplo de
grafo dirigido en el que losa nodos son...
Leer documento completo
Regístrate para leer el documento completo.