Wartości własne. Macierz przyległości. MAXCUT

[neo_gracz]

Witam. Chciałbym zasięgnąć informacji na temat wartości własnych. Moje pytanie brzmi: czy posiadając wiedzę o ilości wierzchołków w grafie oraz jego wszystkich wartościach własnych macierzy przyległosci jesteśmy w stanie dokładnie oszacować problem MAXCUT? Jak to zrobić ? Domyślam się że musimy jakoś odtworzyć tą macierz przyległości. Proszę o naprowadzenie mnie.

[Bugmenot]

• Korzystając ze wszystkich wartości własnych grafu \(\displaystyle{ G}\) można znaleźć liczbę jego krawędzi:
  
  • \(\displaystyle{ \sum\limits^n_{i=1} \lambda^2_i = 2 \cdot |E|}\)
  
  Następnie warto sprawdzić czy zawiera cykle nieparzyste:
  
  • \(\displaystyle{ \forall k \geq 1: \sum\limits^n_{i=0} \lambda^{2k+1}_i \neq 0}\)
  
  Później można skorzystać z twierdzenia:
  
  • graf jest dwudzielny \(\displaystyle{ \Leftrightarrow}\) gdy nie zawiera cykli nieparzystych
  
  Jeżeli okaże się, że graf jest dwudzielny,
  to wartość \(\displaystyle{ MAXCUT = E(G)}\).