Algoritmia Avanzada: Teoría de Grafos

Arno Formella

Curso

La página incial del curso es:

http://formella.webs.uvigo.es/doc/tc03

Estos apuntes se acompaña con ilustraciones en pizarra dónde se explica las notaciones y algunos de los algoritmos.

El texto es meramente una brevísima introducción (5 horas) a la teoría de grafos.

Tareas para una Presentación

El curso de doctorado ya tiene en su título Desarrollo de Software, por eso se ha pensado como tareas:

visualización de grafos:

 
analisis de herramientas disponibles para visualizar grafos y la información que contienen (por ejemplo: AGD)

librerías de programación:

 
analisis de herramientas de programación para trabajar con grafos (por ejemplo: Leda, GraphBase, GTL)

Se pide una breve analisis por lo menos según los siguientes criterios: completitud, complejidad, entorno de uso, algoritmos disponibles, filosofía de diseño, simplicidad de uso, aplicaciones, documentación y recursos disponibles...

Para los que están más interesados en la parte de algoritmia, también hay dos opciones:

caminos más cortos:

busca o desarrolla un algoritmo que enumera todos los caminos más cortos que una variable de entrada k que existen entre dos vértices en un grafo plano.

camino de peso mínimo:

busca o desarrolla un algoritmo que calcule el camino de peso mínimo entre dos vértices en un grafo ponderado, si se permite ciclos de pesos negativos, pero se pone como restricción adicional que ninguna arista se recorre más de una vez (pero si se puede visitar un vértice más de una vez).

Motivación

• plano o mapa de carreteras o calles
• red de flujos (datos, líquidos)
• red de transportes urbanos
• conexiones químicas entre átomos de una molécula
• relación de vecinidad en un mapamundi
• relación de interferencia entre antenas en un sistema de comunicación inalámbrica
• los enlaces entre documentos en el Internet

Es decir, un grafo es el concepto abstracto detrás de la representación de relaciones (aristas) entre entidades (vértices).

Problemas que se quiere resolver:

• Dado un traje completo para vestirse con el fin de ir a una boda en Galicia en invierno, es decir, llueve, ¿En qué orden hay que ponerse las cosas?
• Dado un callejero, ¿Es posible realizar un paseo que recorra cada calle exactamente una vez?
• Dado un callejero, ¿Cuál es el recorrido más corto que debe usar un cartero si tiene que recorrer cada calle por lo menos una vez?
• Dado un callejero, ¿Cómo orientar las calles con sentido único, así que se siga podiendo ir de cada punto a cada punto?
• Dado una fiesta con igual número de chicas y chicos, ¿Cuáles son las condiciones para que sea posible organizar un baile de todos (en parejas chica-chico)?
• Dado una descripción de las interconexiones de un circuito electrónico, ¿Cómo posicionar los chips con sus interconexiones en una placa?
• Dado un conjunto de casas por proteger de fuego, ¿Dónde posicionar los bomberos disponibles para minimizar su radio de acción?

Nociones básicas

Notaciones:

V	conjunto de vértices o nodos
[V]r	conjunto de todos los subconjuntos de V de tamaño r
E $\subseteq$ [V]2	conjunto de aristas
v $\in$ V	vértice
e = {x, y} $\in$ E	arista
{x, y} $\Longleftrightarrow$ : xy	xy es arista
G = (V, E)	grafo
V(G)	vértices del grafo G
E(G)	aristas del grafo G
v $\in$ G : $\Longleftrightarrow$ v $\in$ V(G)	v es vértice del grafo G
e $\in$ G : $\Longleftrightarrow$ e $\in$ E(G)	e es arista del grafo G
| V| = : n	número de vértices
| V| = | V(G)| = | G|	notaciones equivalentes
| E| = : m	número de aristas
| E| = | E(G)| = | G|	notaciones equivalentes

Vocabulario:

trivial	si | G| = 0 o | G| = 1, el grafo es trivial
sobre	si G = (V, E), G es un grafo sobre V
incidente	un vértice v es incidente a una arista e, si v $\in$ e
	una arista e es incidente a un vértice v, si v $\in$ e
adyacente	dos vértices v y w son adyacentes, si {v, w} $\in$ E
conecta	una arista conecta sus vértices
X - Y-arista	si x $\in$ X $\subseteq$ V e y $\in$ Y $\subseteq$ V, xy es X - Y-arista

Notaciones:

E(X, Y)	conjunto de X - Y-aristas
E(v) : = E(v, V $\setminus$ {v})	conjunto de aristas incidentes a v
N(v)	conjunto de vértices adyacentes a v, vecinos
d (v) : = | E(v)| = | N(v)|	grado del vértice v
dG(v)	grado del vértice v $\in$ G
$\delta$(G)	grado mínima de los vértices en G
$\Delta$(G)	grado máxima de los vértices en G
$\epsilon$(G) : = | E|/| V|	grado medio de los vértices en G

Notaciones:

G $\setminus$ e	grafo (V, E $\setminus$ {e})
G $\setminus$ v	grafo (V $\setminus$ {v}, E $\setminus$ E(v))
G $\setminus$ E$\prime$	grafo (V, E $\setminus$ E$\prime$)
G $\setminus$ V$\prime$	grafo (V $\setminus$ V$\prime$, E $\setminus$ E(V$\prime$))

Vocabulario:

vecino	v es vecino de w, si vw $\in$ E(v),
	es decir, si v y w son adyacentes
vecina	e es vecina de f, si e $\cap$ f $\neq$ $\emptyset$
	es decir, e y f son incidentes al mismo vértice
independiente	vértices (o aristas) no adyacentes son independientes;
	un conjunto de vértices (o aristas) que mutuamente son
	independientes es un conjunto independiente
completo	un grafo es completo, si todos sus vértices son vecinos
partición	el conjunto de conjuntos {V0,..., Vr - 1} es una partición de V,
	si V = $\bigcup_{i}^{}$Vi, Vi $\neq$ $\emptyset$, y $\forall$i $\neq$ j : Vi$\bigcap$Vj = $\emptyset$

Notaciones:

$\alpha$(G)

cardinalidad del conjunto de vértices independientes más grande del grafo G

Vocabulario:

digrafo	las aristas están dirigidos, es decir,
	en vez de conjuntos {v, w} se habla de parejas (v, w) o (w, v)
	es decir, E $\subseteq$ V×V
multigrafo	se permite más de una arista entre vértices
pseudografos	se permite bucles en vértices

Representación

Se puede visualizar un grafo pintando sus vértices como puntos y sus aristas como lineas entre los puntos correspondientes.

¿Cuáles son las operaciones que se quiere realizar con un grafo (y sus componentes)?

Se puede almacenar un grafo con

• una matriz de adyacencia
  • matriz cuatrada, y en el caso simple, binaria (y simétrica si no es digrafo) que codifica si existe una arista entre dos vértices
  • complejidad de memoria $\Omega$(n²)
• listas de adyacencia
  • lista o array de vértices que contiene en cada entrada una lista de los vértices adyacentes
  • complejidad de memoria $\Theta$(n + m)
• tablas de dispersion
  • lista o array de vértices que contiene en cada entrada una tabla de dispersion de los vértices adyacentes
  • complejidad de memoria $\Theta$(n + m)

¿Cuáles son las principales ventajas y desventajas de cada uno de los métodos?

Isomorfismo e Invariantes

Sean G = (V, E) y G^$\prime$ = (V^$\prime$, E^$\prime$) dos grafos.

Si existe una bijección $\varphi$ : V $\longrightarrow$ V^$\prime$ entre los vértices de los grafos de tal manera que xy $\in$ E $\Longleftrightarrow$ $\varphi$(x)$\varphi$(y) $\in$ E^$\prime$ (es decir, si x e y son vecinos en G, lo son también $\varphi$(x) y $\varphi$(y) en G^$\prime$), entonces G es isomorfo de G^$\prime$, G $\simeq$ G^$\prime$ o también G = G^$\prime$, es decir, el grafo G.

Una función f sobre grafos con f (G) = f (G^$\prime$) si G $\simeq$ G^$\prime$ se llama invariante. Por ejemplo, invarientes son:

• n
• m
• ¿hay otras?

No se conoce ninguna invariante sobre grafos que se puede calcular en tiempo polinomial que decida que dos grafos son isomorfos, pero tampoco se ha comprobado hasta hoy que el problema de isomorfismo entre grafos sea NP-completo.

Grafos parciales y subgrafos

Sean G = (V, E) y G^$\prime$ = (V^$\prime$, E^$\prime$) dos grafos.

Notaciones:

G $\cup$ G$\prime$ : = (V $\cup$ V$\prime$, E $\cup$ E$\prime$)	unión de grafos
G $\cap$ G$\prime$ : = (V $\cap$ V$\prime$, E $\cap$ E$\prime$)	intersección de grafos

Vocabulario:

grafo parcial	G$\prime$ es grafo parcial de G, V$\prime$ $\subseteq$ V y E$\prime$ $\subseteq$ E
subgrafo	G$\prime$ es subgrafo de G, si G$\prime$ $\cap$ G = G$\prime$,
	es decir, G$\prime$ es un grafo parcial de G que contiene todas
	las aristas de G cuyos vértices incidentes están en V$\prime$.
inducido	si V$\prime$ $\subseteq$ V, el grafo (V$\prime$, E(V$\prime$, V$\prime$)) es el subgrafo G$\prime$ de G inducido por V$\prime$

Notaciones:

G$\prime$ $\subseteq$ G	G$\prime$ es grafo parcial de G
G[V$\prime$]	subgrafo de G sobre V$\prime$ asumiendo V$\prime$ $\subseteq$ V
G[G$\prime$]	subgrafo de G sobre V(G$\prime$) asumiendo G$\prime$ $\subseteq$ G

Vocabulario:

r-partido	un grafo es r-partido, si existe una partición de V
	en r conjuntos independientes
bipartido	2-partido

Grafos especiales

grafos k-regulares: d (G) = $\epsilon$(G) = k    (= $\delta$(G) = $\Delta$(G))

grafos completos K^r: G = (V,[V]²),| V| = r

caminos: P^k: G = ({v₀,..., v_k},{v₀v₁, v₁v₂,...v_{k - 1}v_k})

ciclos C^k: G = ({v₀,..., v_k},{v₀v₁, v₁v₂,...v_{k - 1}v₀})

se puede describir un camino o ciclo por su secuencia de vértices

Vocabulario:

longitud	número de aristas de un camino o ciclo
cíclico	un grafo que contiene un ciclo es cíclico
acíclico	un grafo que no contiene ningún ciclo es acíclico
cintura	un ciclo mínimo que un grafo contiene
circumferencia	ciclo máximo que un grafo contiene

Notaciones:

g(G)	longitud de la cintura de G, ( g(G) = $\infty$ si G acíclico)
D(G)	longitud de la circumferencia de G (D(G) = 0 si G acíclico)

grafos bipartidos B

grafos bipartidos completos K^{n₁, n₂}

hipercubos Q^k

Propiedades (con excepciones para Q⁰ y Q¹):

• n = | V| = 2^k
• k-regular
• bipartidos (¿Cómo particionar?)
• g(Q^k) = 4
• D(Q^k) = 2^k (¿Cuál es un ciclo máximo?)

Conexión

Vocabulario:

componentes conexas

conjunto de subgrafos conexos maximales

Notaciones:

d (v, w)	distancia entre dos vértices siendo la longitud del camino más corto entre v y w
dG(v, w)	distancia entre v y w en G

La distancia define una métrica, es decir,

1. d (v, w) $\geq$ 0
2. d (v, w) = 0 $\Longleftrightarrow$ v = w
3. d (v, w) = d (w, v)
4. d (u, w) $\leq$ d (u, v) + d (v, w)

Vocabulario:

conexo	v y w son conexos, si d (v, w) < $\infty$;
	G es conexo, si todas las parejas v, w $\in$ V son conexos
disconexo	G es disconexo si no es conexo
puente	arista e $\in$ G es un puente, G conexo, tal que G $\setminus$ e es disconexo
vértice de corte	vértice v $\in$ G, G conexo, tal que G $\setminus$ v es disconexo

Notaciones:

c(G)	número de componentes conexas de G
$\kappa$(G)	cardinalidad mínima de un subconjunto de vértices de G
	tal que G $\setminus$ V sea disconexo
$\lambda$(G)	cardinalidad mínima de un subconjunto de aristas de G
	tal que G $\setminus$ E sea disconexo

Vocabulario:

k-conexo	G es k-conexo, si $\kappa$(G) $\geq$ k
biconexo	2-conexo
k-aristoconexo	G es k-aristoconexo, si $\lambda$(G) $\geq$ k
bloque	subgrafo máximo biconexo

Bosques y árboles

• si G no tiene ciclos, G es un bosque
• si G es un bosque y conexo, G es un árbol
• los componentes conexos de un bosque son árboles

Teorema:

las siguientes propiedades son equivalentes:

• G es un árbol
• entre cada pareja de vértices existe un camino único
• cada arista es un puente
• G es acíclico y n = m - 1
• G es conexo y n = m - 1
• G es acíclico y maximal en | E|
• G es conexo y minimal en | E|

Vocabulario:

árbol con raíz	un árbol con un vértice marcado como raíz
árbol libre	un árbol sin marca en ningún vértice
árbol generador	T es árbol generador de un grafo G,
	si T $\subseteq$ G y V(T) = V(G)

Teorema:

cada grafo G contiene un bosque generador, y si G es conexo, contiene un árbol generador (cuya raíz puede ser cualquier vértice)

Recorridos

Vocabulario:

recorrido euleriano	viaje entre dos vértices
	que no pasa varias veces por la misma arista
grafo euleriano	grafo con recorrido euleriano con todas sus aristas
grafo hamiltoniano	grafo con camino por todos sus vértices

Teoremas

Teorema (Euler):

$\sum_{v}^{}$d (v) = 2m

Teorema:

cada grafo tiene un número par de vértices con grado impar

Teorema:

cada grafo G contiene un camino P con | P| $\geq$ $\delta$(G), y cada grafo G con $\delta$(G) $\geq$ 2 contiene un ciclo C con | C| > $\delta$(G)

Teorema:

si G no trivial: $\kappa$(G) $\leq$ $\lambda$(G) $\leq$ $\delta$(G)

Teorema:

cada grafo G con | E| > 1 contiene un subgrafo H con $\delta$(H) > $\epsilon$(H) $\geq$ $\epsilon$(G)

Teorema:

G es bipartido con | V₀| $\neq$ | V₁|          $\Longrightarrow$          G no es hamiltoniano

Teorema:

$\forall$v, w $\in$ V, vw$\notin$E : d (v) + d (w) $\geq$ n          $\Longrightarrow$          G es hamiltoniano

Teorema:

G es hamiltoniano          $\Longrightarrow$          $\forall$S $\subset$ V : c(G $\setminus$ S) $\leq$ | S|

Teorema:

decidir si un grafo G es hamiltoniano es NP-completo

Teorema:

G es bipartido          $\Longleftrightarrow$          G no contiene ciclos impares

¿Algoritmo que decide que G es bipartido?

Teorema:

G es euleriano          $\Longleftrightarrow$          G es conexo y $\forall$v $\in$ V : d (v)    es par

¿Algoritmo que calcule un recorrido euleriano?

Teorema:

G k-conexo          $\Longrightarrow$          | E| $\geq$ $\lceil$kn/2$\rceil$

Teorema (Whitney):

G es 2-conexo (| G| > 2)          $\Longrightarrow$          $\forall$v, w $\in$ V$\exists$vPw, vQw : P $\cap$ Q = $\emptyset$

Es decir, existen dos caminos que no se intersectan entre todas las posibles parejas de vértices en G.

Teorema (Mader):

cada grafo G con $\epsilon$(G) $\geq$ 4k contiene un grafo k-conexo como grafo parcial

Algoritmos básicos

Exploración en profundidad (otros dicen recorrido en profundidad, o depth first search, DFS)

Ejemplo del Algoritmo, se obtiene un árbol con raíz T y aristas de retroceso no pertenecientes a T

• determinar componentes conexas
• detectar puentes
• detectar vértices de corte
• detectar bloques

Teorema:

Sea T un árbol DFS de un grafo G conexo y v su raíz

v es vértice de corte          $\Longleftrightarrow$          v tiene más de un hijo en T

Teorema:

Sea T un árbol DFS de un grafo G conexo y v no sea la raíz

v es vértice de corte          $\Longleftrightarrow$          no existe una arista de retroceso desde el subárbol debajo de v hacia un antecesor de v en T

DFS tiene complejidad $\Theta$(n + m) (asumiendo listas de adyacencias)

Exploración en anchura (otros dicen recorrido en anchura, o breadth first search, BFS)

Ejemplo del Algoritmo, se obtiene un árbol con raíz T, aristas de retroceso no pertenecientes a T, y aristas de cruce

BFS tiene complejidad $\Theta$(n + m) (asumiendo listas de adyacencias)

Grafos dirigidos

Sea G un grafo y $\bar{G}$ un grafo dirigido.

Vocabulario:

fuertemente conexo	$\bar{G}$ es fuertemente conexo, si existe un recorrido
	entre cada pareja de vértices de G
orientable	G es orientable, si existe un grafo $\bar{G}$ $\simeq$ G
	que es fuertemente conexo
componente fuertemente conexa	conjunto máximo de vértices de $\bar{G}$
	cuyo subgrafo inducido es fuertemente conexo

Notaciones:

di(v)	grado entrante
do(v)	grado saliente

Teorema (Robbins):

G orientable          $\Longrightarrow$          G es conexo y no contiene puentes

¿Algoritmo que calcule una orientación?

(¿Qué se entiendo bajo una orientación óptima? Depende: minimizar el promedio de las distancias, minimizar el máximo de las distancias, minimizar el máximo de las diferencias entre las distancias en G y en $\bar{G}$ correspondientes.)

se puede explorar también un digrafo en anchura (BFS) o en profundidad (DFS)

a parte de las aristas del árbol y las aristas de retroceso, DFS produce aristas de progreso y aristas de cruce.

DFS se usa para producir una ordenación topológica de un digrafo acíclico, es decir, en el orden aparece un vértice v antes de un vértice w, si existe un camino desde v a w.

DFS se usa para determinar los componentes fuertemente conexos

¿Algoritmo que calcule los componentes fuertemente conexos?

se puede seguir también recorridos eulerianos:

Teorema:

$\bar{G}$ es euleriano          $\Longleftrightarrow$          $\bar{G}$ es conexo y $\forall$v $\in$ V : d_i(v) = d_o(v)

¿Algoritmo que calcule un camino euleriano en un digrafo?

Grafos ponderados

Notaciones:

(G, W)	grafo ponderado con W : E(G) $\longrightarrow$ $\bbbr^{+}_{}$
w(G)	peso de grafo G, w(G) = $\sum_{e\in G}^{}$w(e)
w(P)	peso de camino P, w(P) = $\sum$e $\in$ Pw(e)
d (v, w)	distancia entre dos vértices, d (v, w) = $\min_{P}^{}${w(vPw)}
dt(v) = $\sum_{w}^{}$d (v, w)	distancia total de un vértice

si w(e) = 1$\forall$e $\in$ E se reproduce la distancia de arriba

Notaciones:

e(v)	excentricidad, e(v) = $\max_{w\in G}^{}${d (v, w)}
rad(G)	radio del grafo G, rad(G) = $\min_{v\in G}^{}${e(v)}
diam(G)	diámetro del grafo G, diam(G) = $\max_{v\in G}^{}${e(v)}

Vocabulario:

centro	el centro del grafo G es el subgrafo de G inducido
	por los vértices con excentricidad mínima
mediana	la mediana del grafo G es el subgrafo de G inducido
	por los vértices con distancia total mínima

Teorema:

G conexo          $\Longrightarrow$          rad(G) $\leq$ diam(G) $\leq$ 2 ^. rad(G)

Teorema:

todo grafo es centro de un grafo

Teorema:

el centro de un árbol consiste en uno o dos vértices

¿Algoritmo que calcule el centro de un árbol?

Árboles generadores y caminos mínimos

dado un grafo G (o un digrafo $\bar{G}$) ponderado

preguntas interesantes:

• ¿Cuál es un bosque generador con peso mínimo en G?
• dado un vertice s $\in$ $\bar{G}$, ¿ Cuáles son los caminos mínimos hacia los demás vértices?
• ¿Cuáles con los caminos mínimos entre todas las parejas de vértices?

hacia cada vértice u $\in$ G existe un camino desde s con distancia mínima

las distancias a todos los vértices en uno de estos caminos a su vez son caminos mínimos

si G es conexo, se puede construir un árbol con raíz s $\in$ G que determina todos los caminos mínimos hacia todos los vértices de G

¿Algoritmo que calcule un bosque mínino de un grafo G?

Algoritmo de KRUSKAL, complejidad O(m log n)

Algoritmo de PRIM, complejidad O(m log n)

¿Algoritmo que calcule un árbol mínimo desde un vértice s en $\bar{G}$?

Algoritmo de DIJKSTRA, complejidad O(n²)

el algoritmo funciona igual con grafos como con digrafos

¿Se puede permitir pesos negativos?

pueden existir ciclos negativos, es decir, ciclos con pesos negativos

¿Algoritmo que calcule un árbol mínimo desde un vértice s en G si G contiene pesos negativos?

Algoritmo de BELLMANN-FORD, complejidad O(mn)

detecta la existencia de ciclos negativos en que caso termina sin solución

¿Algoritmo que calcule los caminos mínimos entre todas las parejas de vértices incluyendo el caso de pesos negativos?

Algoritmo de FLOYD-WARSHALL, complejidad O(n³)

detecta la existencia de ciclos negativos en que caso termina sin solución

Mejoras:

si se tiene más información sobre los grafos y sus pesos se puede mejorar los algoritmos:

• si los pesos están confinados por una constante W:
• si el número de aristas m están confinados por O(n log n):

Minores y Extremalidad

contracción de arista

minor

minor topológico

se puede realizar preguntas interesantes como ciertas propiedades de grafos están relacionados con el tamaño del grafo (normalmente número de aristas)

• ¿Cuántas aristas tiene que tener un grafo como mínimo para que sea un grafo conexo?
• ¿Cuál es el número máximo de aristas que puede tener un grafo para que sea un grafo plano?

Planaridad

Vocabulario:

planar	un grafo es planar cuando se puede pintar sus vértices y sus aristas
	en un plano de tal manera que ninguna pareja de aristas se intersecta
región	una región es un área del plano donde se ha pintado un
	grafo planar que esté confinada por aristas
grafo triangular	un grafo es triangular, si en su representación planar
	en el plano toda región está confinado por tres aristas del grafo

Teorema(Euler):

G planar y conexo con n $\leq$ 1, m y l          $\longrightarrow$          n - m + l = 2

Teorema:

G planar con n $\geq$ 3          $\longrightarrow$          m $\leq$ 3n - 6

Teorema:

G maximal planar si es un grafo triangular (y contiene 3n - 6 aristas)

Teorema(Kuratowski):

G es planar          $\Longleftrightarrow$          no contiene un K⁵ o un K^{3, 3} como minor (o minor topológico)

Coloración

• Coloración de vértices
• Coloración de aristas
• Coloración de grafos planos

Teorema:

G planar          $\longrightarrow$          los vértices de G son colorables con 4 colores

G planar que no contiene ningún triángulo          $\longrightarrow$          los vértices de G son colorables con 3 colores

Notaciones:

$\chi$(G)	número mínimo de colores que se necesita para
	colorar los vértices de un grafo
$\chi^{\prime}_{}$(G)	número mínimo de colores que se necesita para
	colorar las aristas de un grafo

Teorema(Brooks):

G conexo G $\neq$ C^impar y G $\neq$ Kⁿ          $\longrightarrow$          $\chi$(G) $\leq$ $\Delta$(G)

Teorema(Koenig):

G bipartido          $\longrightarrow$          $\chi^{\prime}_{}$(G) = $\Delta$(G)

Flujos

1. Flujos y redes
2. Flujos y cortes
3. Flujos y coloración

Emparejamientos

Teorema:

teorema del matrimonio

Glosario

breve glosario de términos en español y inglés.

árbol	tree
árbol generador	spanning tree
arista de cruce	cross edge
arista de progreso	forward edge
arista de retroceso	back edge
arista	edge
articulación	articulation
bipartido	bipartite
bloque	block
bosque	forest
camino	path
ciclo	cycle
cintura	girth
cliqué	clique
componente	component
conexo	connected
diámetro	diameter
distancia	distance
dirigido	directed
flujo	flow
grado	degree
grafo	graph
hipercubo	hypercube
emparejamiento	matching
nodo	node
peso	weight
ponderado	weighted
puente	bridge
radio	radius
recorrido	walk
vértice de corte	cutvertex

articulación--vértice de corte

vértice de corte--articulación

nodo--vértice--punto

vértice--punto--nodo

punto--nodo--vértice

articulation	articulación
back edge	arista de retroceso
bipartite	bipartido
block	bloque
bridge	puente
clique	cliqué
component	componente
connected	conexo
cross edge	arista de cruce
cutvertex	vértice de corte
cycle	ciclo
degree	grado
diameter	diámetro
directed	dirigido
distance	distancia
edge	arista
flow	flujo
forest	bosque
forward edge	arista de progreso
girth	cintura
graph	grafo
hypercube	hipercubo
matching	emparejamiento
node	nodo
path	camino
radius	radio
spanning tree	árbol generador
tree	árbol
walk	recorrido
weighted	ponderado
weight	peso

Bibliografía

Libros:

 

• Reinhard Diestel. Graph Theory. 2nd edition, Springer Verlag, 2000.
  Existe una versión electrónica no imprimible:
  http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/download.html
• Thomas H. Cormen, Charles E. Leiseron, Ronald L. Rivest. Introduction to Algorithms. McGraw Hill, 1996.

Enlaces:

(como disponibles en noviembre 2003)

• http://www.graphtheory.com
• http://www.ericweisstein.com/encyclopedias/books/GraphTheory.html
• http://mathworld.wolfram.com/Graph.html

Apuntes:

(como disponibles en noviembre 2003)

• Gregorio Hernández Peñalver, Universidad Politécnica de Madrid,
  http://www.dma.fi.upm.es/docencia/segundociclo/teorgraf/home02-03.html
• Steven C. Locke, Florida Atlantic University,
  http://www.math.fau.edu/locke/graphthe.htm