Grafos (Matematicas Discretas)

GRAFO
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 (arcs 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).
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muysencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:
Un conjunto V de puntos llamados vértices o nodos.
‘’‘Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos,denominados aristas o arcos.’‘’

GRAFOS DIRIGIDOS
Un grafo en el cual toda arista es dirigida se denominará "digrafo" o bien "grafo dirigido". Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A.
Los vértices se denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe unarelación univoca.
.

GRAFOS NO DIRIGIDOS:
Un grafo en el cual todas las aristas son no dirigidas se denominará "grafo no dirigido". El grafo no dirigido es aquel que no tiene sentido su arista. Un grafo no dirigido G representa elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.
Si en un Grafo hay aristas dirigidas y aristas no dirigidas, entonces el grafo sedenomina "mixto".

NODO
Nodos (también llamados vértices) se representan con puntos en el grafo.
Un nodo es un elemento constitutivo del hipertexto que contiene una cantidad discreta de información. Nodo es cada elemento que forma parte de la red de información y que puede corresponder bien con las definiciones clásicas de un documento escrito: capítulos, secciones, párrafos, etc.; bien con lasdefiniciones nacidas al albur del mundo digital: porción de texto contenido en la ventana de la pantalla, archivo individual, etc.

RAMAS
Para el análisis que vamos a realizar, consideraremos una rama (línea) por cada componente del circuito, aunque se encuentren en serie.

VALENCIA
El grado o valencia de un vértice es el número de aristas incidentes en él. Para un grafo con bucles, éstosson 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 grado saliente (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
Un ciclo es un camino, es decir unasucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices.
Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y lasaristas los corredores o puertas entre ellas).

RAMAS PARALELAS
El primer término que vamos a conceptualizar es el de Una rama para poder dar seguimiento.
Rama: es una trayectoria dirigida continua de un nodo a otro. También reciben el nombre indistintamente de arcos, aristas o segmentos.
Las ramas paralelas o segmentos múltiples: son aristas que conectan las mismas terminales. Es decir,que del mismo vértice parten 2 o más aristas a otro.
En este ejemplo, hay una única sucursal que se divide en múltiples ramas para poder ejecutarse en paralelas. Usted puede aplicar este ejemplo, para el uso de una pasarela elemento que incluye las ramas que ejecutan en paralelas.
En la siguiente ilustración, rama 0 y rama 1 ejecutan en paralelas.

branch = rama
GRAFOS SIMPLES
Un...