Autor Tema: Bipartito y matriz "incidence"

0 Usuarios y 1 Visitante están viendo este tema.

30 Septiembre, 2014, 03:35 pm
Leído 1732 veces

elcristo

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,201
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Aquí otro problema, del que no logro sacar nada.

Let G be a connected graph with n vertices and m edges, and let BG be its incidence matrix. Show that:
(a) If G is bipartite then the rank of BG is n - 1.
(b) If G is not bipartite then the rank of BG is n.
Clue: There are several ways of doing this. Probably the shortest one is to think of the transpose of BG as the matrix of a linear map Rn --> Rm and to show that its kernel is one-dimensional in case (a) and zero-dimensional in case (b).


Sea G a "connected" grafo con \( n \) vértices y \( m \) aristas, y sea BG la matriz "incidence". Demostrar:
a) Si G es bipartito entonces el rango de BG es \( n-1 \)
b) Si G no es bipartito entonces el rango de BG es \( n \)
Pista: Hay varias formas de hacer esto. Probablemente la mas corta es pensar en la traspuesta de BG como la matriz de la aplicación lineal \( R^n\rightarrow{}R^m \) y demostrar que su núcleo es de dimensión uno en el caso a) y 0 en el caso b).

Posiblemente pueda demostrar que el núcleo en el caso a) es uno y en el caso b) es 0, pero lo que no logro ver es la relación que hay entre eso y la bipartición.