Grafy inaczej, czyli 

inne modele grafów

• Multigrafy
• Grafy z wagami
• Grafy skierowane
• Hipergrafy 

• Grafy losowe (MPK 410, STL 510)

 

 

Multigrafy

• Multigrafy to grafy z wagami na krawędziach; 

wagi to lczby naturalne – krotności krawędzi.

• Problem Chińskiego listonosza: znaleźć 

rozpięty nadgraf eulerowski o najmniejszej 

wadze.

• Inny problem: znaleźć rozpięty nadgraf o 

najmniejszej maksymalnej wadze krawędzi, w 

którym wszystkie stopnie są różne.

• Wariant: jak wyżej, ale chcemy tylko, by pary 

sąsiednich

 wierzchołków miały różne stopnie 

(stopnie w roli kolorów wierzchołków).

• Dla K_n odpowiedź wynosi 3

 

(ćw.)

 

 

Grafy z wagami

• G=(V,E,w), w:E



R

• Wagę podgrafu określamy jako sumę wag 

jego krawędzi.

Klasyczne problemy optymalizacji

:

• MST 

– znaleźć rozpięte drzewo o minimalnej 

wadze.

• Optimal Assignment Problem

 – znaleźć 

skojarzenie doskonałe w grafie dwudzielnym 

K_{n,n} o minimalnej (maksymalnej)  wadze.

• TSP

 – znaleźć cykl Hamiltona o minimalnej 

wadze (problem w klasie 

NP– zupełnej

).

 

 

Parametry ułamkowe

• Skojarzenie ułamkowe 

to funkcja 

w:E 



 [0,1]  taka, że dla każdego v







e

v

e

w

1

)

(

• α’*(G)

 to największa waga 

skojarzenia ułamkowego w grafie 
G, czyli rozwiązanie problemu PL

1

)

(

:

gdy 

,

)

(

 

MAX













e

v

E

e

e

w

v

e

w

 

 

Parametry dualne

• Wierzchołkowe pokrycie ułamkowe 

to funkcja w:V 



 [0,1]  taka, że dla 

każdej krawędzi e=uv

1

)

(

)

(



 v

w

u

w

•  β*(G)

 to najmniejsza waga 

wierzchołkowego     pokrycia 
ułamkowego w grafie G, czyli 
rozwiązanie problemu PL

1

)

(

)

(

:

gdy 

,

)

(

 

MIN













v

w

u

w

G

uv

v

w

V

v

 

 

Twierdzenie o dualności 

PL

• Tw. o dualności

: 

β*(G)=

 

α’*(G)

 – 

tzn. 

ułamkowe tw. Königa

 zachodzi 

dla wszystkich grafów.

• Dla grafów dwudzielnych zachodzi 

tw. 

Königa: 

β(G)=

 

α’(G)

 .

• Zatem, dla grafów dwudzielnych 

α’(G) ≤ α’*(G)

 = 

β*(G)

 

≤ β(G)=

 

α’(G)

,

a więc 

α’(G) = α’*(G)

 .

 

 

Grafy skierowane

Graf skierowany (digraf)

 to para (V,A), 

gdzie A jest zbiorem uporządkowanych 
par różnych wierzchołków z V. 

Elementy zbioru A nazywamy 

łukami

, a na 

rysunkach parę (u,v) przedstawiamy  w 
postaci 

strzałki

 z u do v.

u

v

 

 

Orientacje, turnieje i grafy 

podskórne

• Z (nieskierowanego) grafu G można 

utworzyć graf skierowny nadając 

kierunek każdej krawędzi – 

orientacja

 

grafu G.

• Turniej

 to orientacja grafu pełnego K_n 

• Odwrotnie, z digrafu D można utworzyć 

zwykły (multi)graf G(D) ,,wymazując” 

wszystkie strzałki – tzw. 

podskórny graf 

nieskierowany

 digrafu D.

 

 

Odpowiednik Tw. Diraca

• Półstopnie wejścia i wyjścia

, d^-(v), d^+(v)

Twierdzenie Diraca dla digrafów

. Jeśli 

wszystkie półstopnie wejścia i 
wyjścia są większe bądź równe n/2, 
to D zawiera skierowany cykl 
Hamiltona. 

 

 

Spójność i odpowiednik 

Tw. Eulera

• Digraf D jest 

spójny

, gdy jego graf 

podskórny G(D) jest spójny.

• Digraf D jest 

silnie spójny

, gdy dla 

każdej pary wierzchołków (u,v) 

istnieje w D skierowana ścieżka z u 

do v.

Tw. Eulera dla digrafow.

 Spójny digraf 

D ma skierowany obchód Eulera 

wgdy dla każdego v: d^-(v)=d^+(v).

 

 

Silna spójność orientacji

• Czy dany, spójny system dróg G można 

zmienić na 

jednokierunkowy

, tak, by 

każdy wszędzie mógł (legalnie) dojechać?

• Chodzi tu o silnie spójną orientację grafu 

G.

• Jeśli G ma most, to nie.

Tw. o silnie spójnej orientacji (Robbins 

1939).

 Jeśli G jest 2-krawędziowo-spójny, 

to posiada silnie spójną orientację. 

 

 

Silna spójność turnieju

Tw. (Moon 1966)

 Jeśli D jest silnie spójnym 

turniejem, to dla każdego k=3,…,n każdy 

wierzchołek leży na skierowanym cyklu 

długości k.

Szkic dowodu (ind. wzgl. k): 

• Ustal wierzchołek u i pokaż, że u leży na  

skierowanym trójkącie. 

• Pokaż, ze skoro u leży na cyklu C_k, to leży też 

na cyklu C_{k+1}. 

Wniosek. 

Turniej ma skierowny cykl Hamiltona 

wgdy jest silnie spójny.

 

 

Liczba chromatyczna a 

najdłuższa ścieżka 

skierowana

• Niech l(D) będzie długością najdłuższej 

ścieżki skierowanej w D.

Tw. (Roy 67, Gallai 68)

  χ(G(D)) 

≤

  l(D) +1.

Wniosek.

 χ(G)=min {l(D)+1}, gdzie 

minimum jest wzięte po wszystkich 
orientacjach G.

 

 

Dowód wniosku

Dowod Wniosku: 

Pokolorujmy G 

optymalnie kolorami 1,2,…, χ i 
skierujmy krawędzie od koloru 
mniejszego do większego. Wtedy 
najdłuższa skierowana ścieżka nie 
będzie dłuższa niż χ-1. Nierówność 
w drugą stronę wynika z 

Tw. (Roy 

67, Gallai 68).

 

 

 

Ilustracja

1

2

χ

 

 

Skierowane ścieżki 

Hamiltona w turnieju

Wniosek (Redei, 1934)

 Każdy turniej 

ma ścieżkę Hamiltona.

Dowod:

 Jeśli D jest turniejem, to 

χ(G(D))=n

    i na podstawie 

Tw.

 

(Roy 67, Gallai 68)

 

ma ścieżkę skierowaną długości n-1.

Dowód indukcyjny (

ćw.

)

 

 

Królewskie zbiory 

niezależne

Tw. (Chvatal i Lovasz, 1974) 

Każdy digraf posiada 

zbiór niezależny, z którego każdy inny wierzchołek 

jest osiągalny ścieżką skierowaną długości 1 lub 2.

Szkic dowodu:

 indukcja względem n; w kroku 

indukcyjnym usunąć wierzchołek v wraz ze 

zbiorem sąsiadów N^+(v) (strzałki wychodzące). 

Wniosek.

 Każdy turniej ma króla, tzn. wierzchołek, z 

którego każdy inny wierzchołek jest osiągalny 

ścieżką skierowaną długości 1 lub 2.

Dowod: 

α(G(D))= α(K_n)=1. 

Dowód indukcyjny (

ćw.

)

 

 

Hipergrafy

• Hipergraf 

to para H=(V,E), gdzie E to 

rodzina niepustych pozdbiorów zbioru V.

• V – zbiór wierzchołków, E – zbiór krawędzi
• Hipergraf jest 

k-jednostajny

, gdy wszystkie 

krawędzie mają tę samą moc k.

• Hipergraf 2-jednostajny to po prostu 

graf

.

 

 

Skojarzenia i pokrycia 

hipergrafów

• Skojarzenie

 to zbiór rozłącznych krawędzi.

• α’(H)

 – moc największego skojarzenia w H.

• Pokrycie

 to zbiór wierzchołków, który 

przecina każdą krawędź.

• β(H)

 – moc najmniejszego pokrycia w H.

• Jasne: α’(H) 

≤

 β(H) 

• Problem

: Kiedy α’(H) = β(H) ???

 

 

Problemy NP-zupełne

• W przeciwieństwie do grafów, wyznaczenie α’ 

(H) jest problemem z klasy 

NP-zupełnej.

• Nawet, jeśli ograniczyć sie do hipergrafów 3-

jednostajnych.

• Pokażmy równoważność 

(redukcję 

wielomianową)

 tego problemu z obliczaniem 

α(G):





   α’(H)= α(L(H)), gdzie L(H) – 

graf 

krawędziowy (albo: przecięć)

 hipergrafu H.





   α(G)= α’(St(G)), gdzie St(G) jest 

hipergrafem gwiazd

, tzn. wierzchołkami są 

krawędzie G, a krawędziami są maksymalne 

gwiazdy w G. (

ćw

)

 

 

Hipergrafy 2-kolorowalne

•

H nazywamy 

2-kolorowalnym

, gdy jego 

wierzchołki można pomalować 2 kolorami tak, 

by każda krawędź mocy co najmniej 2 zawierała 

wierzchołki obu kolorów.

•

Podhipergraf indukowany przez U

 to 

H[U]=(U,E’), gdzie E’sklada sie ze wszystkich 

niepustych części wspólnych zbioru U z 

krawędziami H.

•

H jest 

zrównoważony

, gdy każdy podhipergraf 

indukowany jest 2-kolorowalny.

Tw. (Berge i Las Vergnas, 1970)

 Każdy 

zrównoważony hipergraf spełnia własność 

 

Königa: α’(H) = β(H).

 

 

Podhipergraf indukowany