Grafos

INTRODUCCION
Características del grafo:
NODOS
LAZOS O BUCLES
RAMA DE UN GRAFO
GRADO O VALENCIA DE UN GRAFO
CAMINO DE UN GRAFO
TIPO DE GRAFOS: existen dos tipos de grafos los cuales pueden ser Dirigidos y No dirigidos y estos grafos pueden ser: simples, regulares, completos, ciclo, rueda, cubo, bipartidos y bipartidos completos.
REPRESENTACIÓNMATRICIAL DE GRAFOS
Ramas sucesivas de longitud n.
Rama
Ramas paralelas o segmentos múltiples
UN ÁRBOL: es un grafo en el que dos vértices están conectados por exactamente un camino.
BOSQUE: es un grafo en el que dos vértices cualquiera están conectados por como máximo un camino. Una definición equivalente es que un bosque es una unión disjunta de árboles.
GRAFO
Ungrafo es una pareja de conjuntos G = (_V_,_A_), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (_u_,_v_) tal que {draw:frame} , tal que {draw:frame} . Para simplificar, notaremos la arista (_a_,_b_) como ab.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a quévértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.
{draw:a}
En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.
TIPO DE GRAFOS{draw:frame} Un grafo es simple si sólo una arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. {draw:frame}
{draw:frame}
{draw:frame}
{draw:frame}
{draw:frame}
NODOS
Nodos (también llamados vértices) se representan con puntos en el grafo.
LAZOS O BUCLESUn lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.
RAMA DE UN GRAFO
Consideraremos una rama (línea) por cada componente del Grafo, aunque se encuentren en serie.
*GRADO O *VALENCIA DE UN GRAFO
El grado o valencia de un vértice es el número de aristas incidentes al vértice. El grado de un vértice x esdenotado por grado(x), g(x) o gr(x) (aunque también se usa δ(x), y del inglés d(x) y deg(x)). El grado máximo de un grafo G es denotado por Δ(G) y el grado mínimo de un grafo G es denotado por δ(G).
Para un grafo con bucles, éstos son contados por dos. En el ejemplo, los vértices 1 y 3 tienen grado 2; los vértices 2, 4 y 5, grado 3; y el vértice 6, grado 1. En un dígrafo, podemos distinguir el gradosaliente (el número de aristas que dejan el vértice) y el grado entrante (el número de aristas que entran en un vértice). El grado de un vértice sería la suma de ambos números.
CAMINO DE UN GRAFO
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 iníciales y finaldel camino.
La longitud de un camino es el número 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 último.
Un circuito es un camino cerrado que no repite aristas.
Si en un grafo existe un camino queconecta 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...