*Grafos:
Es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o
arcos, que permiten representar relaciones binarias entre elementos de un conjunto.2 Son
objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o
nodos) unidos por líneas (aristas o arcos).
Propiedades
Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos
vértices son adyacentes si una arista los une.
Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
Ponderación: corresponde a una función que a cada arista le asocia un valor (costo,
peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho
para problemas de optimización, como el del vendedor viajero o del camino más
corto.
Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca
que los hace unívocamente distinguibles del resto.
*Vertices:
Es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está
formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de
vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un
conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados
como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional
dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es
un grafo en donde los vértices representan conceptos o clases de objetos.
*Aristas:
Corresponde a una relación entre dos vértices de un grafo. En un grafo no dirigido, se trata
de relaciones simétricas sin dirección, mientras que en un grafo dirigido son relaciones
direccionales, también conocidas como arcos.2
Para caracterizar un grafo G son suficientes únicamente el conjunto de todas sus aristas,
comúnmente denotado con la letra E (del término en inglés edge), junto con el conjunto de
sus vértices, denotado por V. Así, dicho grafo se puede representar como G(V,E), o bien G
= (V,E).
Grado de un vértice
En teoría gráfica , el grado de un vértice es el número de bordes que lo conectan. En el
ejemplo siguiente, el vértice a tiene grado 5, y el resto tienen grado 1. Un vértice con grado
1 es llamado un "vértice final" (puede ver porque).
Representación Grafica
Un grafo se representa mediante un diagrama en el cual a cada vértice le
corresponde un punto y si dos vértices son adyacentes se unen sus puntos
Correspondientes mediante una línea, ejemplo:
*Tipos de Grafos:
Grafo
Un grafo es un conjunto de vértice o nodos unidos por aristas o arcos.
Grafo acíclico
Es aquel grafo no contiene ningún ciclo simple.
Grafo cíclico
Un grafo se dice cíclico si contiene algún ciclo simple.
Grafo bipartito
Un grafo bipartito es cualquier grafo, cuyos vértices pueden ser divididos en dos
conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. Se ve que
un grafo es bipartito si no hay ciclos de longitud impar.
Grafo completo
Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el
número de vértice que compone el grafo. Además es un grafo simple en el que
cada vértice es adyacente a cualquier todo otro vértice.
Grafo conexo
Decimos que es un grafo conexo, si es posible formar un camino desde cualquier
vértice a cualquier otro en el grafo.
Grafo denso
Un grafo denso es aquel grafo en el que el número de aristas está cercano al
número de máximo de aristas.
Grafo dirigido
Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista
perteneciente al conjunto de aristas E se asocia con dos vértices en forma
ordenada.
Grafo no dirigido
Son aquellos grafos en los cuales los lados no están orientados (no son flechas).
Cada lado se representa entre paréntesis, separando sus vértices por comas
Grafo nulo
El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.
Grafo plano
Un grafo plano es uno que es posible dibujar en el plano sin que ningún par de
aristas se crucen entre sí.
Grafo ponderado
Un grafo ponderado es aquel que asocia un valor o peso a cada arista en el grafo.
El peso de un camino en un grafo con pesos es la suma de los pesos de todas las
aristas atravesadas.
Grafo regular
Un grafo regular es un grafo cuyos vértices tienen el mismo grado.
Grafo simple
Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es
un multígrafo.
Grafo no Simple:
Grafo no dirigido que tiene lados paralelos y lazos.
Grafo trivial
Un grafo trivial es aquel grafo vacío con un único vértice.
Grafo vacío
Un grafo vacío es el grafo cuyo conjunto de aristas es vacío.
*Arboles:
Es un grafo en el que cualquier par de vértices están conectados por exactamente un
camino, o alternativamente, es un grafo conexo acíclico.1
Un bosque es un grafo disconexo acíclico. Alternativamente, se puede definir como una
unión disjunta de árboles, es decir, es un grafo disconexo cuyas componentes son árboles.
ÁRBOLES GENERADORES MÍNIMOS
Definición:
El peso de un árbol generador es la suma de los pesos de las ramas del árbol. Un árbol
generador mínimo es uno con peso mínimo.
Una interpretación física de este problema es considerar los vértices de un grafo como
ciudades, y los pesos de las aristas como los costos de construcción y mantenimiento de
vías de comunicación entre las ciudades. Supongamos que queremos construir una red de
comunicaciones que conecte a todas las ciudades a un costo mínimo. Entonces el problema
es determinar un árbol generador mínimo.
Ejemplo:
*Coloración de Grafos:
Es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a
elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún
vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista
coloración asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y
una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que
caras que compartan una frontera común tengan colores diferentes. El vértice coloración es el
punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una
versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice
coloración del grafo línea respectivo, y una coloración de caras de un grafo plano es una vértice
coloración del grafo dual.
*Propiedades (Link de abajo).
[Link]
grafos
