Grafos

Grafos: 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). Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entreunidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representanconexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).grafo etiquetado con 6 vertices y 7 aristas

En teoría de grafos, un vértice o nodo es la unidad fundamental de la queestá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 unconjunto de vértices y un conjunto de arcos (pares ordenados de vértices).

En teoría de grafos, una arista corresponde a una relación entre dos vértices de un grafo. Para caracterizar un grafo G sonsuficientes ú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 sepuede representar como G(V,E), o bien G = (V,E). Un vértice es incidente a una arista si pertenece a ésta, o en otras palabras, si está conectado a otro vértice (o a él mismo) a través de ella. Unsubgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H(dependiendo de las necesidades de la situación). El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G. Definición: Sea G=(V, A)....