Recomendamos este sitio, algunos de los contenidos presentados a continuación los tomados de Wolfram MathWorld
Un grafo G es un par (V,E) donde V es un conjunto llamado de vértices y E un subconjunto llamado de VxV (conjunto de aristas).
Gráficamente representaremos los vértices por puntos y las aristas por líneas que los unen.
Un vértice puede tener 0 o más aristas, pero toda arista debe unir exatamente 2 vértices.
Llamaremos orden de un grafo a su número de vertices, |V|.
Si |V| es finito se dice que el grafo es finito.
Aristas: Si la arista carece de dirección se denota indistintamente {a,b} o {b,a}, siendo a y b se les llama sus extremos.
Vértice: Dos vértices v, w se dice que son adyacentes si {v,w} ÎA (o sea, si existe una arista entre ellos). 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. CAMINO: 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}, {v1v2},..., {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
- 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.
Si quieres conocer más ingresa a nuestra etiqueta sobre Euler y Hamilton.