La teorÃa de grafos (también llamada teorÃa de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacÃo, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no.
TÃpicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por lÃneas (las aristas).
TIPOS
NO DIRIGIDOS
Son aquellos 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, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).
DIRIGIDOS
Son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.
VERTICES
Un vértice o nodo es la unidad fundamental de la que están formados los grafos. 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.
ARCO
El arco es la union que se se tiene entre dos vertices, cada arco se representa a traves de un par, donde cada elemento determina uno de los vertices.
CAMINOS
Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo. Otras definiciones básicas son:
Los extremos son los vértices inicial y final del camino.
La longitud de un camino es el numero de aristas que contiene.
Un camino es cerrado si sus extremos coinciden.
Un camino es simple si en la sucesión de vértices no hay ninguno repetido.
Un ciclo es un camino cerrado donde los únicos vértices repetidos son el primero y el ultimo.
Un circuito es un camino cerrado que no repite aristas.
Si en un grafo existe un camino que conecta dos vértices distintos, entonces existe un camino simple con extremos en dichos vértices.
Un grafo es conexo si para cada par de vértices, existe un camino con extremos en dichos vértices.
Tipos de caminos
Camino euleriano:
es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar.
Camino hamiltoniano:
es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.
No hay comentarios:
Publicar un comentario