MATERIAS DE ESCUELA Y COLEGIO

GRAFOS

Un grafo 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 , tal que.Para simplificar, notaremos la arista (a,b) como ab.

»Multígrafo: Cuando hay 2 o más aristas paralelas, o cuando 2 vértices están relacionados más veces con sigo mismo.






»Dígrafo: Hay unpunto de origen y uno de destino final, es decir: no pueden ser a,b = b,a.





-QUE ES UNA ARISTA:
Son las líneas con las que se unen los vértices de un grafo, los vértices a y b son losextremos.

»Arista Adyacente: 2 aristas son adyacentes si convergen en el mismo vértice.

»Arista Paralelas: Son dos aristas conjuntas si el vértice inicial y final son el mismo.

»Arista Cíclicos:Es la arista que parte de un vértice para entrar en el mismo.

»Cruce: Son 2 aristas que cruzan en un mismo punto.










-QUE ES UN VÉRTICE:

Los vértices son los dos elementos queforman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices.
Diferentes situaciones en las que pueden identificarseobjetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.









Tipos de grafos (Simples, completos, bipartidos, planos,conexos, ponderados)

Grafos simples.- Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que unedos vértices específicos. Un grafo que no es simple se denomina multígrafo.









Grafo completo.- Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Esdecir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn el grafo completo de n vértices. Un Kn, es decir,...