Definición. (Gráfica)
Un gráfica
es una terna ordenada , consiste del conjunto de vértices o nodos, (disjunto de ) bordes o aristas, y una función de incidencia que asocia cada borde de un par no ordenado de vértices de (no necesariamente distintos). Si
y tales que , entonces se dice que une y ; los vértices son llamados extremos de .
Ejemplo
donde
y
se define por Posibles diagramas de la gráfica
:
Def. (Gráfica Simple, Completa, Vacía)
Una gráfica es simple si no tiene bucles y no más de una arista une un par de vértices (inyectiva).
Una gráfica simple, la cual cada par de vertices distintos incide una arista, es llamada gráfica completa. Tal gráfica con
vértices; es denotada . La gráfica vacía es la que no tiene aristas.
Ejemplo
Observamos además que
es planar.
Definiciones Básicas
- Una gráfica planar tiene algún diagrama cuyas aristas se intersectan únicamente por sus extremos.
- Los extremos de algún
son incidentes con la arista, y viceversa. - Dos vértices que son incidentes a una arista común, son adyacentes, y viceversa.
- Una arista con extremos iguales, es un loop (bucle) o lazo. ej.
- Una arista con extremos diferentes, es un link o enlace. ej. todos menos
. - Una mutligráfica es una grafica con lazos y aristas paralelas.
- La gráfica con un solo vértice es la trivial, todas las demás son no-triviales.
y denotan el número de vértices y aristas de . - En ocasiones se omite
ej.
Resultados
Teorema
Si
es simple, entonces .