Definicje — grafy

• Graf spójny
• Graf dwudzielny

Graf spójny

Graf $G(V,E)$ jest spójny jeśli $\forall v_i,v_j \in V$ istnieje droga od $v_i$ do $v_j$

Graf dwudzielny

Graf $G(V,E)$ jest dwudzielny jeśli $V$ możemy podzielić na dwa podzbiory $A,B: A \dot\cup B = V$ przy czym wierzchołki z każdego z tych podzbiorów mogą się łączyć tylko z wierzchołkami z drugiego podzbioru, nie pomiędzy sobą.

Innymi słowy, graf w którym każdy cykl ma parzystą długość.

dowód z wykładu