Graf dwudzielny.

[dawhyp]

Dobry wieczór,
nie wiedziałem gdzie umiescic dokładnie ten temat. Otóż zgodnie z definicją graf dwudzielny jest to graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru.

@Edit: Już się z tym uporałem. Mam za to inne pytanie:

Załóżmy, że mamy graf w postaci:
\(\displaystyle{ B -- C \\
| \ \ \ \ \ \ \ \ | \\
A \ \ \ \ \ \ D}\)

Czy mogę go nieco przekształcić, tj. narysować jako:
\(\displaystyle{ \ \ \ \ \ \ \ \ \ D \\
\ \ \ \ \ \ \ \ \ \ \ \\
B -- C \\
| \\
A}\)

Połączenie punktów jest to samo, więc wydaje mi się, że to nadal ten sam graf. Ale wolę się upewnić. (Między C i D jest krawędź).

[lemoid]

Przekształcenie nie jest w tym przypadku najlepszym określeniem.

Sposób zapisu graficznego zależy od Ciebie, ważne by zachować krawędzie między odpowiednimi wierzchołkami.

Graf nieskierowany można sobie przedstawić na przykład tak

Kod: Zaznacz cały

A
|
B
|
C
|
D

można też tak:

Kod: Zaznacz cały

D-C-B-A

albo tak

Kod: Zaznacz cały

A
 
   B
    
     C
      
       D