Tienen vértices
adyacentes entre sí y
n(n-1)/2 aristas.
Caminos Simples
Caminos Simples (Pn)
Son grafos
lineales sin ciclos,
tienen n vértices
y n-1 aristas
Gráfica Dirigida
Las aristas que
unen a los nodos
tienen una
dirección
representada
por flechas
Digráfica Simple
No
contiene
búcles ni
líneas
paralelas
Tiene n vértices y
k componentes y
tiene a lo más
(n-k)(n-k+1) líneas
Digráfica Simétrica
Por cada arco que une
a los nodos Vi a Vj
existe uno que los une
de Vj a Vi.
Digráfica Completa
Se denota como
DKn donde n es el
número de nodos y
todos sus nodos
tienen arcos
paralelos de ida y
regreso.
Digráfica Asimétrica Completa
También llamada
"Torneo completo" y
para cada par de
nodos existe una
linea dirigida
Tiene n(n-1)/2 líneas
Digráfica Regular
Es de grado (i, e)
donde todos los
nodos tienen el
mismo grado interno
y externo
Digráfica Balanceada
Cada nodo tiene
grado interno =
externo
Bosques
Conformada por varios árboles
Los árboles son gráficas
simples conectadas sin
circuitos
Árbol Binario
tiene un vértice de
grado 2 y los restantes
son de grado 1 o 3
Árbol Estrictamente Binario
Cada nodo tiene
0, 1 o 2 hijos
Subgráficas
Todos los vértices de
g están contenidos en
G y cada línea de g
tiene los mismos
vértices de terminales
en G
Gráfica Bipartita
El conjunto de vértices puede dividirse en
dos subconjuntos donde las vértices de un
subconjunto no deben ser adyacentes a los
elementos del otro subconjunto
Gráfica Bipartita Completa
Todos los nodos de un
subconjunto son
adyacentes los nodos
del otro subconjunto
Multigrafo o Pseudografo
Tiene líneas paralelas y búcles
Tamaño de G:
Es el número de
aristas que
tiene una
gráfica
Orden de G:
Es el número
de nodos
que tiene
una gráfica
Trivial. Gráfica
que consta de
un sólo nodo
Incidencia y Adyacencia
Un nodo es terminal de un
arco, el nodo incide en el arco
o la línea incide en él
Dos arcos no paralelos son
incidentes de un nodo en común
o dos nodos comparten una
línea, son adyacentes