Teoría de grafos - Árboles

Los árboles son gráficos que no contienen ni un solo ciclo. Representan la estructura jerárquica en forma gráfica. Los árboles pertenecen a la clase más simple de gráficos. A pesar de su sencillez, tienen una estructura rica.

Los árboles proporcionan una gama de aplicaciones útiles tan simples como un árbol genealógico hasta tan complejas como los árboles en las estructuras de datos de la informática.

Árbol

UNA connected acyclic graphse llama árbol. En otras palabras, un gráfico conectado sin ciclos se llama árbol.

Los bordes de un árbol se conocen como branches. Los elementos de los árboles se denominan nodos. Los nodos sin nodos secundarios se denominanleaf nodes.

Un árbol con 'n' vértices tiene 'n-1' aristas. Si tiene una arista más que 'n-1', entonces la arista extra debería obviamente emparejarse con dos vértices, lo que lleva a formar un ciclo. Luego, se convierte en un gráfico cíclico que es una violación del gráfico de árbol.

Example 1

El gráfico que se muestra aquí es un árbol porque no tiene ciclos y está conectado. Tiene cuatro vértices y tres aristas, es decir, para 'n' vértices 'n-1' aristas como se menciona en la definición.

Note - Cada árbol tiene al menos dos vértices de grado uno.

Example 2

En el ejemplo anterior, los vértices 'a' y 'd' tienen grado uno. Y los otros dos vértices 'b' y 'c' tienen grado dos. Esto es posible porque para no formar un ciclo, debe haber al menos dos aristas simples en cualquier parte del gráfico. No son más que dos aristas con un grado de uno.

Bosque

UNA disconnected acyclic graphse llama bosque. En otras palabras, una colección desarticulada de árboles se llama bosque.

Example

El siguiente gráfico parece dos subgráficos; pero es un solo gráfico desconectado. No hay ciclos en este gráfico. Por tanto, claramente es un bosque.

Árboles de expansión

Sea G un gráfico conectado, entonces el subgráfico H de G se llama árbol de expansión de G si -

  • H es un árbol
  • H contiene todos los vértices de G.

Un árbol de expansión T de un grafo no dirigido G es un subgrafo que incluye todos los vértices de G.

Example

En el ejemplo anterior, G es un gráfico conectado y H es un subgráfico de G.

Claramente, el gráfico H no tiene ciclos, es un árbol con seis aristas que es uno menos que el número total de vértices. Por tanto, H es el árbol de expansión de G.

Rango de circuito

Sea 'G' un gráfico conectado con 'n' vértices y 'm' aristas. Un árbol de expansión 'T' de G contiene (n-1) aristas.

Por lo tanto, la cantidad de aristas que necesita eliminar de 'G' para obtener un árbol de expansión = m- (n-1), que se denomina rango de circuito de G.

Esta fórmula es cierta, porque en un árbol de expansión necesita tener aristas 'n-1'. Fuera de los bordes 'm', debe mantener los bordes 'n – 1' en el gráfico.

Por lo tanto, eliminar los bordes 'n – 1' de 'm' da los bordes que se deben eliminar del gráfico para obtener un árbol de expansión, que no debería formar un ciclo.

Example

Eche un vistazo al siguiente gráfico:

Para el gráfico dado en el ejemplo anterior, tiene m = 7 aristas yn = 5 vértices.

Entonces el rango del circuito es -

G = m - (n - 1)

= 7 - (5 - 1)

= 3

Example

Sea 'G' una gráfica conectada con seis vértices y el grado de cada vértice es tres. Encuentre el rango del circuito de 'G'.

Por la suma del teorema del grado de vértices,

n Σ i=1grados (V i ) = 2 | E |

6 × 3 = 2 | E |

| E | = 9

Rango de circuito = | E | - (| V | - 1)

= 9 - (6 - 1) = 4

Teorema de Kirchoff

El teorema de Kirchoff es útil para encontrar el número de árboles de expansión que se pueden formar a partir de un gráfico conectado.

Example

La matriz 'A' debe rellenarse como, si hay una arista entre dos vértices, entonces se debe dar como '1', en caso contrario, como '0'.

$$ A = \ begin {vmatrix} 0 & a & b & c & d \\ a & 0 & 1 & 1 & 1 \\ b & 1 & 0 & 0 & 1 \\ c & 1 & 0 & 0 & 1 \\ d & 1 & 1 & 1 & 0 \ end {vmatrix} = \ begin {vmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \ end {vmatrix} $$

Al usar el teorema de kirchoff, debería cambiarse reemplazando los valores diagonales principales con el grado de los vértices y todos los demás elementos con -1.

$$ = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = M $$ $$ M = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = 8 $$ $$ Co \: \: factor \: \: of \: \: m1 \: \: = \ begin {vmatrix } 2 & 0 & -1 \\ 0 & 2 & -1 \\ - 1 & -1 & 3 \ end {vmatrix} $$

Por tanto, el número de árboles de expansión = 8.