Dopełnienie grafu prostego
Jeśli G jest grafem prostym z F(G), to dopełnieniem jest graf prosty G , którego zbiorem wierzchołków jest F(G) i w którym dwa wierzchołki są sąsiednie wtedy i tylko wtedy, gdy nie są sąsiednie w grafie G.
Graf platonski
graf regularny utworzony przez wierzchołki i krawędzie jednego z pięciu wielościanów foremnych ( czworościanu, sześcianu, ośmiościanu, dwunastościanu lub dwudziestościanu).
Np. graf czworościanu (K4):
Graf dwudzielny
Graf jest dwudzielny, jeżeli zbiór wierzchołków grafu G można podzielić na dwa rozłączne zbiory Vx i V2 w taki sposób, że każda krawędź grafu G łączy dowolny wierzchołek zbioru V1 z dowolnym wierzchołkiem zbioru V2.
W grafie dwudzielnym wierzchołki da się pomalować dwoma kolorami tak, że każda krawędź ma jeden koniec innego koloru niż drugi koniec
Pełny graf dwudzielny
graf prosty, dwudzielny i to taki, że każdy wierzchołek zbioru V1 jest połączony z każdym wierzchołkiem zbioru V2.
Oznaczamy Kr s, gdzie r i s są liczbami wierzchołków odpowiednio w
Vx i V2.
Pełny graf dwudzielny Kj - gwiazda
Graf ogólny
Uwalniamy się od ograniczenia, że każda krawędź musi łączyć dwa różne wierzchołki oraz że co najwyżej jedna krawędź łączy parę wierzchołków.
—> możliwość występowania pętli (krawędzi łączących wierzchołki same ze sobą) oraz krawędzi wielokrotnych.
Obiekt, w którym dozwolone są pętle oraz krawędzie wielokrotne
graf (ogólny)
F(G) = { u, v, w, z }
E(G) = { {u,v}, {v,v}, {v,w}, {v,w}, {v,w}, {u,w}, {u,w}, {w,z} }
Każdy graf prosty jest grafem ogólnym, ale nie każdy graf ogólny jest grafem prostym.
Dwa wierzchołki grafu są sąsiednie, jeżeli istnieje krawędź łącząca je.
Wierzchołek stopnia zero
— izolowany.
Wierzchołek stopnia jeden
— końcowy (wiszący).
Graf regularny - graf, w którym każdy wierzchołek ma taki sam stopień.
Jeżeli każdy wierzchołek jest stopnia r, to graf jest regularny stopnia r. Np. K4 - kubiczny (tzn. regularny stopnia 3).
Graf cykliczny - graf spójny, regularny, stopnia 2.
Graf cykliczny o n wierzchołkach oznaczamy C„.
Graf liniowy - graf otrzymany z grafu C„ przez usunięcie jednej krawędzi.
Oznaczamy P„.
Koło - graf powstały z grafu C„ przez połączenie każdego wierzchołka z nowym wierzchołkiem v.
GRAFY
Graf prosty G - para (F(G), E(G))
gdzie:
F(G) - niepusty, skończony zbiór elementów zwanych wierzchołkami (węzłami, punktami),
E(G) — skończony zbiór różnych, nieuporządkowanych par różnych (w parach) elementów zbioru F(G) zwanych krawędziami
Izomorfizm
Dwa grafy G2 i G2 są izomorficzne, jeśli istnieje wzajemnie jednoznaczna odpowiedniość między wierzchołkami grafu G2 i wierzchołkami grafu G2 taka, że liczba krawędzi łączących dowolne dwa wierzchołki w G2 jest równa liczbie krawędzi łączących odpowiadające im wierzchołki
W zagadnieniach, gdzie nazwy są zbędne, pomijamy je ->■ grafy
nieoznakowane (w przeciwieństwie do oznakowanych czyli takich, gdzie wierzchołkom są przyporządkowane nazwy).
Dwa nieoznakowane grafy są izomorficzne, jeżeli możemy tak przyporządkować nazwy wierzchołkom, by otrzymane grafy oznakowane były izomorficzne.
Odrzucanie
Jeżeli e jest krawędzią grafu G, to G - e jest grafem otrzymanym z G po odrzuceniu krawędzi e.
Jeżeli v jest wierzchołkiem grafu G, to G - v jest grafem otrzymanym z G
po usunięciu z G wierzchołka v wraz z przyległymi do niego
krawędziami.
Ściągniecie
G \ e — graf otrzymany w wyniku ściągnięcia krawędzi e i utożsamienia jej końców v oraz w i to w taki sposób, że otrzymany wierzchołek jest incydentny z tymi krawędziami, które przedtem były incydentne z v i w (z wyjątkiem krawędzi e).
Podgraf grafu G
graf, którego wszystkie wierzchołki należą do F(G) i wszystkie krawędzie należą do E(G)
Graf pusty - graf, którego zbiór krawędzi jest pusty (bezkrawędziowy). Oznaczamy N„.
Graf pełny — graf prosty, w którym każde dwa różne wierzchołki są sąsiednie. Oznaczamy K„.
Macierz sąsiedztwa:
Jeśli w grafie G wierzchołki są oznakowane liczbami ze zbioru {1,...,«}, to macierz sąsiedztwa A jest macierzą wymiaru n\n, której wyraz o indeksach i,j jest równy liczbie krawędzi łączących wierzchołek / z wierzchołkiem j.
Macierz incydencji:
Jeśli w grafie G dodatkowo oznakujemy krawędzie liczbami ze zbioru {1,..., m}, to macierzą incydencji nazywamy macierz wymiaru ram, której wyraz o indeksach /,/ jest równy 1, jeśli wierzchołek / jest incydentny z krawędzią j, a równy 0 w przeciwnym przypadku
Spójność grafu
Graf jest spójny, gdy nie może być przedstawiony w postaci sumy dwóch grafów.
Graf jest spójny, gdy dowolna para wierzchołków grafu jest połączona drogą.
Graf niespójny - w przeciwnym przypadku.
Dowolny niespójny graf może być przedstawiony jako suma skończonej liczby grafów spójnych, zwanych składowymi spójnymi grafu
Twierdzenie:
Każdy graf prosty, który ma n wierzchołków i więcej niż (n-l)(n-2)/2 krawędzi, jest spójny.
Suma dwóch grafów
G2 = (F(G2), E(G2)) F(Gi) i F(G2)- rozłączne
Suma Gx U G2- graf ze zbiorem wierzchołków F(Gi) U V(G2) i rodziną krawędzi ^Gj) U E(G2)
Zespolenie dwóch grafów
G2 = (F(G2), j) i F(G2)- rozłączne
Zespolenie Gj + G2 — bierzemy sumę G2 u G2 i prowadzimy krawędzie z każdego wierzchołka F(Gj) do każdego wierzchołka F(G2).
Trasa (marszruta) w grafie G - skończony ciąg krawędzi
v„ -> v, -> v2 ->... -> vm
w którym każde dwie kolejne krawędzie są albo sąsiednie, albo identyczne.
długość trasy - liczba krawędzi w trasie. Trasa wyznacza pewien ciąg wierzchołków, gdzie v0 -początek, vm - koniec
Ścieżka (łańcuch) - trasa, w której wszystkie krawędzie są różne. Droga - ścieżka, w której ponadto wszystkie wierzchołki są różne.
Ścieżka lub droga są zamknięte, gdy v0 = vm.
Cykl— Droga zamknięta zawierającą przynajmniej jedną krawędź Obwód grafu - długość najkrótszego cyklu w tym grafie
Zbiór rozdzielający grafu spójnego G
— zbiór wierzchołków, których usunięcie spowoduje, że graf przestanie być spójny.
Spójność wierzchołkowa K(G)
— Jeżeli graf G jest spójny i nie jest pełny, to spójnością wierzchołkową grafu G nazywamy liczbę elementów najmniejszego zbioru rozdzielającego.
Graf jest A-spójny wierzchołkowo, jeśli K (G) > k.
Wierzchołek rozcinający
- Jeżeli zbiór rozdzielający składa się tylko z jednego wierzchołka, to ten wierzchołek nazywamy wierzchołkiem rozcinającym
Zbiór rozspajający grafu spójnego G
- zbiór krawędzi, których usunięcie spowoduje, że graf G przestanie być
spójny.
Rozcięcie - zbiór rozspajający, którego żaden podzbiór właściwy nie jest już zbiorem rozpajającym
Most
—jeżeli rozcięcie składa się z jednej krawędzi, to krawędź tę nazywamy mostem
Spójność krawędziowa ^G) - w grafie spójnym jest to liczba krawędzi należących do najmniej licznego rozcięcia grafu.
Tzn. jest to najmniejsza liczba krawędzi, które należy usunąć, aby graf przestał być spójny.
Graf jest A-spójny krawfdziowo, jeśli X (G) > k.
Grafy eulerowskie
Graf spójny G nazywamy grafem eulerowskim, jeżeli istnieje ścieżka zamknięta zawierająca każdą krawędź G.
Taką ścieżkę nazywamy cyklem Eulera.
Uwaga: nazwa „cykF, choć od cyklu żąda się by był drogą. Niekonsekwencja ze względu na tradycyjną nazwę.
Jak narysować ten graf bez odrywania ołówka i bez rysowania tej samej linii wielokrotnie?
Grafy póleulerowskie
Graf, który nie jest grafem eulerowskim, nazywamy półeulerowskim, jeżeli istnieje ścieżka zawierająca każdą krawędź grafu G.
Twierdzenie (Euler, 1776): Graf spójny G jest grafem eulerowskim
wtedy i tylko wtedy, gdy stopień każdego wierzchołka grafu G jest liczbą parzystą.
Twierdzenie'. Graf spójny G jest grafem półeulerowskim wtedy i tylko wtedy, gdy ma dokładnie dwa wierzchołki nieparzystych stopni.
W grafie półeulerowskim każda ścieżka Eulera musi zaczynać sif w jednym wierzchołku nieparzystego stopnia i kończyć w drugim takim wierzchołku.
Uwaga: żaden graf nie może mieć dokładnie jednego wierzchołka nieparzystego stopnia.
To wynika z lematu o uściskach dłoni: jeśli pewne osoby witają się podając sobie dłonie, to łączna liczba uściśniętych dłoni jest parzysta.
W każdym grafie suma stopni wszystkich wierzchołków jest liczbą parzystą.
W każdym grafie liczba wierzchołków o nieparzystych stopniach jest parzysta.
Algorytm Fleury'ego
służy do konstrukcji cyklu Eulera w grafie eulerowskim
Zacznij cykl w dowolnym wierzchołku u i przechodź krawędzie w dowolnej kolejności, dbając jedynie o zachowanie następujących reguł:
(1) usuwaj z grafu przechodzone krawędzie i wierzchołki izolowane
powstające w wyniku usuwania krawędzi;
(2) w każdym momencie przechodź przez most tylko wtedy, gdy nie
masz innej możliwości.
Graf z zamknieta sciezka przechodzaca dokladnie jeden raz przez każdy wierzcholek to graf hamiltonowski
Grafpólhamiltonowski
graf, który nie jest hamiltonowski i w którym istnieje droga przechodząca dokładnie jeden raz przez każdy wierzchołek
Dla grafów hamiltonowskich nie ma udowodnionych warunków koniecznych i wystarczających takich, jak w przypadku grafów eulerowskich.
Twierdzenie (Dirac, 1952): Jeżeli w grafie prostym Gon wierzchołkach (n > 3), stopień każdego wierzchołka jest większy bądź równy n/2, to graf G jest hamiltonowski.
Twierdzenie (Ore, 1960): Jeśli graf prosty G ma n wierzchołków (n > 3) oraz suma stopni dowolnych dwóch wierzchołków, które nie są sąsiednie, jest większa od n, to graf G jest hamiltonowski.
Zagadnienie chińskiego listonosza
Zadanie polega na tym, by listonosz, który musi doręczyć pocztę, przeszedł jak najkrótszą łączną drogę i powrócił do punktu wyjścia.
Znaleźć taką trasę zamkniętą, której całkowita waga jest minimalna i w której każda krawędź występuje co najmniej jeden raz.
Jeśli graf jest grafem eulerowskim, to każdy cykl Eulera jest poszukiwaną
trasą. Jeśli graf nie jest eulerowski — zadanie trudniejsze.
Drzewa
Las - graf, który nie zawiera cykli Drzewo - las spójny
Jeżeli graf G jest lasem, który ma n wierzchołków i k składowych, to G ma n—k krawędzi.
Własności drzew
Niech T - graf o n wierzchołkach będący drzewem
(1)T nie zawiera cykli i ma n—l krawędzi
(2)T jest grafem spójnym i każda krawędź jest mostem
(3)Każde dwa wierzchołki T są połączone dokładnie jedną drogą
(4)T nie zawiera cykli, ale po dodaniu dowolnej nowej krawędzi otrzymamy graf z dokładnie jednym cyklem
(5) W każdym drzewie są przynajmniej dwa wierzchołki wiszące
Drzewo z wyróżnionym korzeniem
drzewo, w którym wyróżniono jeden z wierzchołków
Numer poziomu wierzchołka v — długość drogi od korzenia do v Wysokość drzewa — największy numer poziomu wierzchołka.
Tylko liście mogą mieć numer poziomu równy wysokości drzewa
Drzewa spinające
Dopóki w grafie spójnym są cykle: wybieramy cykl w grafie G,
usuwamy którąś krawędź cyklu graf pozostaje spójny i
powstaje drzewo, które spina wszystkie wierzchołki grafu
drzewo spinające grafu G - podgraf grafu G będący drzewem i zawierający wszystkie wierzchołki G
Każdy graf spójny ma drzewo spinające
G dowolny graf o n wierzchołkach i m krawędziach oraz
k składowych stosujemy procedurę do każdej składowej G => las spinający
Rząd cykliczności (liczba cyklomatyczna) grafu G: y(G) - łączna liczba usuniętych krawędzi
y(G) = m-n+k
Rząd rozcięcia (rząd spójności) grafu G: - liczba krawędzi w lesie spinającym
: Dopełnieniem lasu spinającego T grafu G (niekoniecznie prostego) nazywamy graf otrzymany z grafu G przez usunięcie krawędzi należących do T.
Twierdzenie:
Jeśli T jest lasem spinającym grafu G, to:
(a)każde rozcięcie grafu G ma wspólną krawędź z T
(b)każdy cykl w grafie G ma wspólną krawędź z dopełnieniem T.
Algorytm Kruskala
Niech G - graf spójny o n wierzchołkach.
(1) wybieramy krawędź el o najmniejszej wadze,
(2) definiujemy krawędzie e2, e3,..., en_x wybierając za
każdym razem nową krawędź o najmniejszej możliwej
wadze, która nie tworzy cyklu z dotychczas wybranymi
krawędziami ei.
Podgraf T grafu G, którego krawędziami są krawędzie ev e2,..., enA jest szukanym drzewem spinającym
Algorytm Prima
Niech G - graf spójny o n wierzchołkach.
E:=0
Wybierz w ze zbioru V(G) i V := {w}
Dopóki V * V(G) wykonuj
wybierz w zbiorze E(G) krawędź {u ,v} o najmniejszej możliwej
wadze taką, że u e V i v e V(G)—V dołącz krawędź {u , v} do zbioru E i wierzchołek v do zbioru V.
Też algorytm zachłanny. W każdym kroku szukana jest krawędź o
najmniejszej wadze łącząca jakiś wierzchołek istniejącego do tej pory drzewa spinającego T z nowym wierzchołkiem spoza T.
Grafy planarne
Graf płaski - graf narysowany na płaszczyźnie w taki sposób, że żadne dwie krawędzie nie przecinają się geometrycznie z wyjątkiem wierzchołków, z którymi sąincydentne.
Graf planarny - graf izomorficzny z grafem płaskim
(graf jest planarny, jeśli może być umieszczony na płaszczyźnie w taki sposób, że takie jego przedstawienie jest grafem płaskim)
Homeomorfizm grafów
Dwa grafy se homeomorficzne, jeśli mogą być otrzymane z tego samego grafu poprzez umieszczenie nowych wierzchołków stopnia 2 na jego krawędziach.
Twierdzenie (Kuratowski, 1930):
Graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z £3 3 i K5.
Ściany graf u płaskiego
Jeśli G jest grafem planarnym, to każdy rysunek płaski grafu G dzieli zbiór punktów płaszczyzny, które nie leżą na G na obszary zwane ścianami.
Twierdzenie Eulera:
Niech G będzie rysunkiem płaskim spójnego grafu planarnego i niech n, m i/oznaczają odpowiednio liczbę wierzchołków, krawędzi i ścian grafu G. Wtedy:
n-m+f= 2
Twierdzenie:
Niech G jest grafem płaskim mającym n wierzchołków, m krawędzi, /ścian oraz k składowych spójnych. Wtedy:
n-m+f=k+l
Grafy dualne
Jeśli mamy dany rysunek płaski grafu planarnego G, to konstruujemy graf G*, który nazywamy grafem (geometrycznie) dualnym do grafu G w następujący sposób:
(1)wewnątrz każdej ściany/grafu G wybieramy punkt v* te punkty będąwierzchołkami grafu G*;
(2)dla każdej krawędzi e grafu G prowadzimy linię e* przecinającą e (alenie przecinającą żadnej innej krawędzi grafu G) i łączącą wierzchołki
v* ścian/oddzielonych od siebie krawędzią e - linie te będąkrawędziami grafu G*.
Twierdzenie:
Niech G będzie spójnym grafem płaskim mającym n wierzchołków, m krawędzi i/ścian oraz niech graf G* geometrycznie dualny do niego ma n* wierzchołków, m* krawędzi i/* ścian. Wtedy:
n=f rn=m f*=n
Kolorowanie grafów
Kolorowanie wierzchołków
Mając dany graf, pokolorować jego wierzchołki w taki sposób, aby każde dwa wierzchołki sąsiednie miały inny kolor.
Każda krawędź łączy wierzchołki różnych kolorów.
Takie pokolorowanie nazywać będziemy właściwym.
Definicja:
Graf jest A>kolorowalny (wierzchołkowo), jeśli każdemu wierzchołkowi możemy przypisać jeden z k kolorów tak, że żadne dwa wierzchołki sąsiednie nie mają tego samego koloru.
Definicja:
Jeśli G jest A>kolorowalny, ale nie jest (A>l)-kolorowalny to mówimy, że graf jest ^-chromatyczny.
Definicja:
Liczbą chromatyczną grafu %(G) nazywamy najmniejszą
liczbę kolorów niezbędną do właściwego pokolorowania
wierzchołków grafu.
Graf 4-chromatyczny
Do pokolorowania grafu pełnego Kn potrzeba n kolorów (wszystkie jego wierzchołki są sąsiednie).
Graf zawierający graf pełny
o r wierzchołkach jest co najmniej
r-chromatyczny.
Drzewa:
Każde drzewo o dwóch lub więcej wierzchołkach jest 2-chromatyczne
Twierdzenie:
Jeśli G jest grafem prostym, w którym największy stopień wierzchołka wynosi d, to graf G jest (</+l)-kolorowalny.
górne ograniczenie liczby chromatycznej
Twierdzenie:
Jeśli G jest spójnym grafem prostym, nie będącym grafem pełnym i jeśli największy stopień wierzchołka grafu G wynosi d (d > 3), to graf G jest </-kolorowalny (tzn.x(G)<<Q.
Gdy wszystkie stopnie wierzchołków są w przybliżeniu takie same -można mieć korzyść z twierdzenia.
Ale np. K, s - z twierdzenia wynika, że graf ten jest s-kolorowamy, a naprawdę jest 2-kolorowalny dla każdego s.
Jeśli ograniczymy rozważania do grafów planarnych, to:
Twierdzenie o czterech barwach (Appel, Haken, 1976):
KAŻDY PLANARNY GRAF PROSTY JEST 4-KOLOROWALNY
Kontrastowe kolorowanie grafów
Dodatkowy warunek — wierzchołki sąsiadujące otrzymują kolory, których odległość nie należy do pewnego ustalonego zbioru T.
Zastosowanie: problem przydziału częstotliwości, układanie rozkładów zajęć itd.
Inne: sumacyjne (minimalna „suma kolorów"),
listowe (dla każdego wierzchołka zbiór dopuszczalnych kolorów jest ograniczony przez pewien podzbiór)...
Wielomiany chromatyczne
G-graf prosty.
PG(k) - liczba sposobów pokolorowania właściwego wierzchołków grafu G dysponując k kolorami.
Np. jeśli G jest drzewem
o 3 wierzchołkach
Funkcja PG(k) - wielomian chromatyczny grafu G
Jeśli graf G ma n wierzchołków, to wielomian PG(k) ma stopień n ze współczynnikiem 1 przy k".
Wyraz wolny dowolnego wielomianu chromatycznego jest
równy 0 ( grafu nie można pokolorować, gdy k = 0, czyli nie mamy żadnego koloru).
Twierdzenie:
Niech G będzie grafem prostym i niech G—e oraz G\e będą grafami otrzymanymi z G przez usunięcie i ściągnięcie krawędzi e. Wówczas:
Kolorowanie krawędzi
Graf G jest A>barwny krawędziowo (A>barwny(e)), gdy jego krawędzie można tak pokolorować k barwami, aby żadne dwie krawędzie sąsiednie nie miały tego samego koloru.
Gdy graf G jest A>barwny(e), lecz nie jest (M)-barwny(e), to jego liczba chromatyczna krawędziowa - indeks chromatyczny %'(G) - wynosi k.
Twierdzenie:
Jeśli G jest grafem prostym, którego największy stopień wierzchołka wynosi d, to d < x'(G) ^ d+1.
Dokładne określenie, które grafy mają %'(G)=d, a które %'(G)= d+\, jest problemem.
Np. %'(C„) = 2, gdy n jest parzyste lub %'(C„) = 3, gdy n jest nieparzyste. Np. x'(^«) = n? gdy n jest nieparzyste, x'(^«) = n-l, gdy n jest parzyste.
Twierdzenie:
Jeśli G jest grafem dwudzielnym z maksymalnym stopniem wierzchołka d, to %'(G) = d.
Mapa - graf planarny 3-spójny.
Nie zawiera rozcięć mających 1 lub dwie krawędzie. Nie ma wierzchołków stopnia 1 i 2.
Mapa jest A>kolorowalna (/), jeśli jej ściany można pokolorować k kolorami tak, by żadne dwie ściany ograniczone wspólną krawędzią nie były pomalowane tym samym kolorem.
Twierdzenie:
Niech G będzie grafem planarnym bez pętli i niech G* będzie grafem geometrycznie dualnym do grafu G.
Graf G jest £-kolorowalny(v) wtedy i tylko wtedy, gdy graf G* jest £-kolorowalny(/).
Dla dowolnego twierdzenia dotyczącego kolorowania wierzchołków grafu planarnego możemy utworzyć twierdzenie dualne mówiące o kolorowaniu ścian mapy.
Twierdzenie o czterech barwach dla map jest równoważne z twierdzeniem o czterech barwach dla grafów planarnych.
Pokrycia w grafach
GrafG(F,£)
Pokryciem krawędziowym grafu nazywamy taki podzbiór jego krawędzi,
że każdy wierzchołek grafu jest incydentny z przynajmniej jedną
krawędzią tego podzbioru.
Pokryciem wierzchołkowym grafu nazywamy taki podzbiór jego
wierzchołków, że każda krawędź grafu jest incydentna z przynajmniej jednym wierzchołkiem z tego podzbioru.
Zbiory wewnętrznie stabilne
Wierzchołki v1; v2 nazywamy niezależnymi, gdy nie są wierzchołkami sąsiednimi.
Zbiorem wewnętrznie stabilnym wierzchołków grafu G nazywamy dowolny podzbiór wierzchołków parami niezależnych.
Skojarzenia
Krawędzie ex, e2 grafu nazywamy niezależnymi, jeśli nie są incydentne ze wspólnym wierzchołkiem.
Skojarzeniem w grafie nazywamy dowolny podzbiór krawędzi parami niezależnych.
Skojarzenia w grafach dwudzielnych
Graf dwudzielny G( Vx u V2, E)
Skojarzeniem całkowitym ze zbioru Vx w zbiór V2 grafu dwudzielnego G(VluV2, E) nazywamy takie skojarzenie w grafie G, że dla każdego wierzchołka v e Vl istnieje w skojarzeniu krawędź incydentna z tym wierzchołkiem.
TwierdzenieHalla (wersja grafowa):
Niech G = G(F1uF2, E) będzie grafem dwudzielnym i niech dla każdego podzbioru A zbioru Vl zbiór <p(A) będzie zbiorem tych wierzchołków należących do V2, które sąsiadują z co najmniej jednym wierzchołkiem ze zbioru A.
Istnieje skojarzenie całkowite z Vl do V2 wtedy i tylko wtedy, gdy dla każdego podzbioru A zbioru Vl zachodzi nierówność \A\ < \q>(A)\
Transwersale
Rodzina zbiorów - pewna uporządkowana lista zbiorów F = (S1,... ,Sm) Niech A - niepusty zbiór skończony S, - niepuste podzbiory A
Transwersalą rodziny F (systemem różnych reprezentantów) nazywamy zbiór m różnych elementów zbioru A, wybranych po jednym z każdego zbioru Su
Twierdzenie Halla ( wersja transwersalowa):
Niech A będzie niepustym zbiorem skończonym i niech F = (St,..., Sm) będzie rodzina niepustych podzbiorów zbioru A. Rodzina F ma transwersale wtedy i tylko wtedy, gdy suma dowolnych k podzbiorów St ma co najmniej k elementów ( dla 1 < k < ni).