15 Algunos grafos notables

Definición 15.1.

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

Proposición 15.1.

El grafo completo Kn\displaystyle K_{n} tiene las siguientes propiedades:

  •  
    ​

    El numero de vertices es n\displaystyle n

  •  
    ​

    El grado de cada vertice es g⁢r⁢(v1)=⋯=g⁢r⁢(vn)=n−1\displaystyle gr(v_{1})=\cdots=gr(v_{n})=n-1

  •  
    ​

    El numero de aristas, usando el Teorema de Euler es

    |E|=12⁢∑i=1ng⁢r⁢(vi)=12⁢∑i=1n(n−1)=n⁢(n−1)2\displaystyle|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

    (011⋯1101⋯1110⋯1⋯⋯⋯⋯⋯111⋯0)\displaystyle\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 1n×n−In\displaystyle{\large{1}_{n\times n}}-I_{n}.

Definición 15.2 (Grafo bipartido).

Se dice que un grafo simple G=(V,E)\displaystyle G=(V,E) es bipartido si su conjunto de vertices V\displaystyle V se puede expresar como la unión de dos subconjuntos no vacios disjuntos V1\displaystyle V_{1} y V2\displaystyle V_{2} de manera que cada arista del grafo conecta un vertice de V1\displaystyle V_{1} con un vertice de V2\displaystyle V_{2}. Esto es, no existe una arista entre dos vertices de V1\displaystyle V_{1} ni entre dos vertices de V2\displaystyle V_{2}: si {u,v}∈E\displaystyle\{u,v\}\in E entonces |{u,v}∩Vi|=1\displaystyle|\{u,v\}\cap V_{i}|=1, i=1,2\displaystyle 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.

Definición 15.3 (Grafo bipartido completo).

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

  •  
    ​

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

Ejemplo.

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

  •  
    ​

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

  •  
    ​

    Grado de los vertices: Si v∈V1⇒g⁢r⁢(v)=m\displaystyle v\in V_{1}\Rightarrow gr(v)=m. Si v∈V2⇒g⁢r⁢(v)=n\displaystyle v\in V_{2}\Rightarrow gr(v)=n.

  •  
    ​

    Numero de aristas: Usando el teorema de Euler, 2⁢|E|=∑v∈Vg⁢r⁢(v)=∑v∈V1g⁢r⁢(v)+∑v∈V2g⁢r⁢(v)=m⋅n+n⋅m=2⋅m⋅n⇒|E|=n⋅m\displaystyle 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 V1={v1,…,vn}\displaystyle V_{1}=\{v_{1},\ldots,v_{n}\} y V2={w1,…,wm}\displaystyle V_{2}=\{w_{1},\ldots,w_{m}\}. Tomando el orden de vertices v1,…,vn,w1,…,wm\displaystyle v_{1},\ldots,v_{n},w_{1},\ldots,w_{m} la matriz de adyacencia es

    A=(00⋯01⋯100⋯01⋯1⋯⋯⋯⋯⋯⋯⋯00⋯01⋯111⋯10⋯0⋯⋯⋯⋯⋯⋯⋯11⋯10⋯0)=(0n×n1n×m1m×n0m×m)\displaystyle 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)