15 Algunos grafos notables

Definition 15.1.

Se denomina grafo completo de $n$ vertices al grafo simple de $n$ vertices $K_{n}=(\left\{1,2,\ldots,n\right\},\left\{\left\{i,j\right\};1\leq i<j\leq n% \right\})$ . Esto significa que cada par de vertices distintos son adyacentes.

Proposition 15.2.

El grafo completo $K_{n}$ tiene las siguientes propiedades:

•

El numero de vertices es $n$
•

El grado de cada vertice es $gr(v_{1})=\cdots=gr(v_{n})=n-1$
•

El numero de aristas, usando el Teorema de Euler es

$|E|=\frac{1}{2}\sum_{i=1}^{n}gr(v_{i})=\frac{1}{2}\sum_{i=1}^{n}(n-1)=\frac{n(% n-1)}{2}$
•

Su matriz de adyacencia es

$\begin{pmatrix}0&1&1&\cdots&1\\ 1&0&1&\cdots&1\\ 1&1&0&\cdots&1\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ 1&1&1&\cdots&0\\ \end{pmatrix}$

o equivalentemente ${{1}_{n\times n}}-I_{n}$ .

Definition 15.3 (Grafo bipartido).

Se dice que un grafo simple $G=(V,E)$ es bipartido si su conjunto de vertices $V$ se puede expresar como la unión de dos subconjuntos no vacios disjuntos $V_{1}$ y $V_{2}$ de manera que cada arista del grafo conecta un vertice de $V_{1}$ con un vertice de $V_{2}$ . Esto es, no existe una arista entre dos vertices de $V_{1}$ ni entre dos vertices de $V_{2}$ : si $\left\{u,v\right\}\in E$ entonces $|\left\{u,v\right\}\cap V_{i}|=1$ , $i=1,2$ .

¿Cómo saber si un grafo es bipartido?

•

Si contiene un ciclo con una cantidad impar de vertices NO puede ser bipartido.
•

Existe un algoritmo para saber si es bipartido o no que, en caso de que lo sea, nos da la bipartición del conjunto de vértices.

Definition 15.4 (Grafo bipartido completo).

Sea $V_{1}=\left\{1,\ldots,m\right\}$ y $V_{2}=\left\{1^{\prime},\ldots,n^{\prime}\right\}$ . El grafo bipartido completo $K_{m,n}=(V,E)$ se define como $V=V_{1}\cup V_{2}$ y $E=\left\{\left\{j,k^{\prime}\right\}\colon j\in V_{1},k^{\prime}\in V_{2}\right\}$ . Esto es, $V$ se puede expresar como la union de dos subconjuntos disjuntos $V_{1}$ de $m$ vertices y $V_{2}$ de $n$ vertices, de manera que cada vertice de $V_{1}$ esta conectado con todos los vertices de $V_{2}$ y ninguna arista conecta un par de vertices de $V_{1}$ ni de $V_{2}$ .

•

En general los grafos bipartidos son diferentes de los grafos bipartidos completos.

Example 15.5.

Calcular el numero de vertices, grados, numero de aristas y matriz de adyacencia del grafo $K_{n,m}(n,m\in\mathbb{N})$

•

Numero de vertices: Si $K_{n,m}=(V,E)$ , entonces $V=V_{1}\cup V_{2}$ particion de $V$ con $V_{1}$ conjunto de $n$ vectores y $V_{2}$ conjunto de $m$ vectores $\Rightarrow$ el numero de vertices es $|V|=|V_{1}|+|V_{2}|=n+m$
•

Grado de los vertices: Si $v\in V_{1}\Rightarrow gr(v)=m$ . Si $v\in V_{2}\Rightarrow gr(v)=n$ .
•

Numero de aristas: Usando el teorema de Euler, $2|E|=\sum_{v\in V}gr(v)=\sum_{v\in V_{1}}gr(v)+\sum_{v\in V_{2}}gr(v)=m\cdot n% +n\cdot m=2\cdot m\cdot n\Rightarrow|E|=n\cdot m$
•

Matriz de adyacencia: Si denotamos $V_{1}=\left\{v_{1},\ldots,v_{n}\right\}$ y $V_{2}=\left\{w_{1},\ldots,w_{m}\right\}$ .

Tomando el orden de vertices $v_{1},\ldots,v_{n},w_{1},\ldots,w_{m}$ la matriz de adyacencia es

$A=\begin{pmatrix}0&0&\cdots&0&1&\cdots&1\\ 0&0&\cdots&0&1&\cdots&1\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ 0&0&\cdots&0&1&\cdots&1\\ 1&1&\cdots&1&0&\cdots&0\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ 1&1&\cdots&1&0&\cdots&0\\ \end{pmatrix}=\left(\begin{array}[pos]{c|c}0_{n\times n}&1_{n\times m}\\ \hline\cr 1_{m\times n}&0_{m\times m}\\ \end{array}\right)$