Conceptos Basicos De Grafos

Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.


→Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
→Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
→Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
→Cruce: Son dos aristas que cruzan en un punto.

Vértices: Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es ‘par’ o ‘impar’ según lo sea su grado.

→Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
→Vértice Aislado: Es un vértice de grado cero.
→Vértice Terminal: Es un vértice de grado 1.

Caminos: Sean x, y Î V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},…, {vn,y}. En este caso

→x e y se llaman los extremos del camino
→El número de aristas del camino se llama la longitud del camino.
→Si los vértices no se repiten el camino se dice propio o simple.
→Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
→Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
→Llamaremos ciclo a un circuito simple
→Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo