Grafo recorrible
Clasificado en Matemáticas
Escrito el en 
español con un tamaño de 2,31 KB
C) Para un grafo G con numero cromático x su índice corresponderá a x+1// C)Esto aplica solo para los grafos sin un ciclo de largo impar, ya que por lo general en ese caso el número cromático seria ≥ índice cromático, si el grafo no tiene ciclos de largo impar, el numero cromático es igual a el índice cromático menos 1, no a el índice cromático mas 1.
Sea T un árbol en que cada vértice tiene grado 1 o grado k, con k >= 2. Mostrar que |V(G)| - 2 es múltiplo de k – 1 // a=Cantidad de nodos de grado 1 b=Cantidad de nodos de grado k, a+b=Cantidad de nodos de T Re (a + b) + |V(G)| - 2 = 2 |V(G)| - 2 , 2 |V(G)| - 2 = 2 (|V(G)| - 1), {prop árbol} 2 (|V(G)| - 1) = 2|E(G)| teo handsh 2|E(G)|=Zδ(v)=a+bk || (a+b)+|V(G)|-2 = a+bk (restar (a + b)) || |V(G)| - 2 = bk – b
7) Se asume q G contiene un número finito d vértices y aristas. Además, se sabe q un matching perfecto es aquel que cubre todos los vértices de un grafo. Si G contiene 2 matching perfectos, llamados A y B, estos tendrán al menos una arista distinta. Los vértices de dicha arista deben pertenecer a aristas pertenecientes a B (recordar que ambos son matching perfectos). Dibujando entonces estas dos aristas recién mencionadas se sigue. Luego, siguiendo el razonamiento anterior, las aristas pertenecientes a B tendrán vértices en común con algunas aristas de A. En este punto se pueden dar dos casos.
Por contradicción: Se supone lo contrario, es decir, que no hay matching completo. Por lo tanto, para contradecir el teorema de hall, Existe al menos un A subconjunto de X tal que: |N(A)| Sea un x Є A, donde x no posee matching. Por lo tanto, se asumirá que hay un matching completo para A-{x}, por lo que se tiene que: |N(A)| = |N(A-{x})| = |A|-1 En donde nuestro |N(A)|, tendrá el mismo valor que |N(A-{x})|, donde se excluye a x que no tiene matching y así |N(A-{x})| no tiene matching y así|A| - 1 será el valor de la función N. Como se contradice el teorema de Hall QD.
Sea T un árbol en que cada vértice tiene grado 1 o grado k, con k >= 2. Mostrar que |V(G)| - 2 es múltiplo de k – 1 // a=Cantidad de nodos de grado 1 b=Cantidad de nodos de grado k, a+b=Cantidad de nodos de T Re (a + b) + |V(G)| - 2 = 2 |V(G)| - 2 , 2 |V(G)| - 2 = 2 (|V(G)| - 1), {prop árbol} 2 (|V(G)| - 1) = 2|E(G)| teo handsh 2|E(G)|=Zδ(v)=a+bk || (a+b)+|V(G)|-2 = a+bk (restar (a + b)) || |V(G)| - 2 = bk – b
7) Se asume q G contiene un número finito d vértices y aristas. Además, se sabe q un matching perfecto es aquel que cubre todos los vértices de un grafo. Si G contiene 2 matching perfectos, llamados A y B, estos tendrán al menos una arista distinta. Los vértices de dicha arista deben pertenecer a aristas pertenecientes a B (recordar que ambos son matching perfectos). Dibujando entonces estas dos aristas recién mencionadas se sigue. Luego, siguiendo el razonamiento anterior, las aristas pertenecientes a B tendrán vértices en común con algunas aristas de A. En este punto se pueden dar dos casos.
Por contradicción: Se supone lo contrario, es decir, que no hay matching completo. Por lo tanto, para contradecir el teorema de hall, Existe al menos un A subconjunto de X tal que: |N(A)| Sea un x Є A, donde x no posee matching. Por lo tanto, se asumirá que hay un matching completo para A-{x}, por lo que se tiene que: |N(A)| = |N(A-{x})| = |A|-1 En donde nuestro |N(A)|, tendrá el mismo valor que |N(A-{x})|, donde se excluye a x que no tiene matching y así |N(A-{x})| no tiene matching y así|A| - 1 será el valor de la función N. Como se contradice el teorema de Hall QD.