2004897
Description
Mind Map by richy.mac2014, updated more than 1 year ago
|
Created by richy.mac2014
over 9 years ago
|
|
Teoría de Gráficas
- Grafos
G(V,A)
V=Vértices
A=Aristas
- Tipos de Grafos
- Grafos Completos (Kn)
- Tienen vértices
adyacentes entre sí y
n(n-1)/2 aristas.
- Caminos Simples
- Tienen vértices
adyacentes entre sí y
n(n-1)/2 aristas.
- Caminos Simples (Pn)
- Son grafos
lineales sin ciclos,
tienen n vértices
y n-1 aristas
- 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
- No
contiene
búcles ni
líneas
paralelas
- Digráfica Simétrica
- Por cada arco que une
a los nodos Vi a Vj
existe uno que los une
de Vj a Vi.
- 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.
- 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
- También llamada
"Torneo completo" y
para cada par de
nodos existe una
linea dirigida
- Digráfica Regular
- Es de grado (i, e)
donde todos los
nodos tienen el
mismo grado interno
y externo
- 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
- Cada nodo tiene
grado interno =
externo
- Digráfica Simple
- Las aristas que
unen a los nodos
tienen una
dirección
representada
por flechas
- 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
- 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
- Cada nodo tiene
0, 1 o 2 hijos
- Árbol Binario
- Los árboles son gráficas
simples conectadas sin
circuitos
- Conformada por varios árboles
- 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
- 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
- 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
- Todos los nodos de un
subconjunto son
adyacentes los nodos
del otro subconjunto
- Multigrafo o Pseudografo
- Tiene líneas paralelas y búcles
- Tiene líneas paralelas y búcles
- Grafos Completos (Kn)
- 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
- 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
- Un nodo es terminal de un
arco, el nodo incide en el arco
o la línea incide en él
- Tipos de Grafos
- Teoremas
- Havel Hakimi
- Lema del apretón de manos
- Nodos de grado impar son par
- Nodos aislados son de grado 0
- Nodos de grado 1 son colgantes
- Nodos de grado impar son par
- Gráfica desconectada
- Gráfica simple
de n vertices y k
subconjuntos
- Tiene a lo más (n-k)(n-k+1)/2 líneas
- Tiene a lo más (n-k)(n-k+1)/2 líneas
- Havel Hakimi
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.