4 Nociones básicas

Las notaciones que se suelen usar en la teoría de grafos son muy intuitivas y se basan ya casi siempre en la nomen clatura inglesa. Se aprovecha de interpretaciones sencillas y expresivas de los símbolos disponibles desde otras ramas de la matemática.

Notaciones:

$V$	conjunto de vértices o nodos (o a veces, puntos)
$[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$
$\vert V\vert =: n$	número de vértices
$\vert V\vert=\vert V(G)\vert=\vert G\vert$	notaciones equivalentes
$\vert E\vert =: m$	número de aristas
$\vert E\vert=\vert E(G)\vert=\Vert G\Vert$	notaciones equivalentes

Vocabulario:

trivial	si $\vert G\vert=0$ o $\vert G\vert=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):=\vert E(v)\vert=\vert N(v)\vert$	grado del vértice $v$
$d_G(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):=\vert E\vert/\vert V\vert$	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 $\{V_0,...,V_{r-1}\}$ es una partición de $V$,
	si $V=\bigcup_{i}V_i$, $V_i\neq\emptyset$, y $\forall i\neq j: V_i\bigcap V_j=\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\times V$
multigrafo	se permite más de una arista entre vértices
pseudografos	se permite bucles en vértices

Es decir, en la mayoría de los casos se entiende como grafo solamente el caso en el cual existe como mucho una arista (o arista dirigida) entre dos vertices diferentes.