MATEMATYKA DYSKRETNA
Skrypt pisany na podstawie wykładu prowadzonego przez
Dr. T. Traczyka
Wiadomości wstępne
Tw. O indukcji matematycznej
Zasada szufladkowa Dirichleta
Jeżeli do n szuflad włożymy n+1 przedmiotów, to w co najmniej jednej szufladzie będzie 2 lub więcej przedmiotów.
Definicje
Def. Grafem nazywamy parę gdzie – zbiór (skończony) niepusty,
- zbiór wierzchołków
- zbiór krawędzi
Def. Stopniem wierzchołka w grafie jest liczba
Def. wtedy v – izolowany
wtedy v – liść
Def. , u-v drogą w G nazywamy ciąg gdzie
1)
2)
3)
Liczbę k nazywamy długością drogi. Jeżeli ponadto to jest drogą prostą.
Def. G jest grafem spójnym u-v droga w
Def. Jeżeli w drodze to drogę nazywamy cyklem. Jeżeli w drodze prostej sąsiaduje z , to drogę nazywamy cyklem prostym.
Def. Dopełnieniem grafu nazywamy graf . W dopełnieniu grafu G sąsiadują te, i tylko te wierzchołki, które nie sąsiadowały w G.
Graf i jego dopełnienie.
Def. jest pograłem
Graf i jego podgraf.
Def. H jest nadgrafem G G jest podgrafem H.
Def. jest pograłem indukowanym
Graf i jego podgraf indukowany.
Def. H jest podgrafem rozpinającym w
Graf i jego podgraf rozpinający.
Def. Najmniejszy stopień wierzchołka w grafie G -
Def. Największy stopień wierzchołka w grafie G -
Def. G jest r-regularny
Graf 4-regularny o 7 wierzchołkach.
Def. - graf pełny o n wierzchołkach -
Grafy pełne.
Def. i są izomorficzne .
Izomorfizm grafów oznacza się
Def. Graf jest acykliczny wtedy i tylko wtedy, kiedy nie zawiera cykli.
Def. Grafem krawędziowym grafu G nazywamy graf L(G) taki, że istnieje bijekcja z V(G) do E(L(G)) taka, że wierzchołki odpowiadające krawędziom e i f w grafie G są połączone krawędzią w L(G) e i f mają wspólny wierzchołek w G.
Grafy i .
Twierdzenia
Lemat O uściskach dłoni.
Lemat w G istnieje pewien cykl (prosty).
Spójność
Def. Graf G jest k-spójny (wierzchołkowo) spójny). Spójnością grafu G nazywamy największe k takie, ze G jest k-spójny i oznaczamy .
Def. Graf G jest l-spójny krawędziowo spójny). Spójnością krawędziową grafu G nazywamy największe l takie, ze G jest l-spójny krawędziowo i oznaczamy
Def. - ilość sąsiadów podzbioru S
Def. i. Zbiór jest x-y oddzielający każda x-y droga przechodzi przez S w G-S x i y są w różnych składowych.
Tw. W grafie prostym mającym n wierzchołków, k składowych i m krawędzi zachodzi nierówność:
Tw. Whitney’a
Tw. Graf jest dwuspójny każde dwa wierzchołki z G leża na pewnym cyklu prostym
Tw. Halla (o zawieraniu małżeństw)
G – graf dwudzielny X na Y. G ma niezależnych krawędzi . Powyższy warunek nosi nazwę warunku Halla.
Tw. Mengera (1927)
Jeśli dla każdego u-v zbioru rozdzielającego S mamy , to w G istnieje k rozłącznych u-v dróg.
Tw. Këniga – Halla
W każdym grafie dwudzielnym .
Drzewa
Def. Drzewem nazywamy spójny graf acykliczny.
Def. Lasem nazywamy graf acykliczny.
Def. Promieniem grafu nazywamy liczbę
Def. jest wierzchołkiem centralnym w
Tw. Następujące warunki są równoważne:
1) jest drzewem.
2) droga) i jest to droga prosta (”istnieje dokładnie jeden”).
3) G jest spójny i .
4) G jest acykliczny i .
5) G jest spójny i jest niespójny.
6) G jest acykliczny i posiada cykl i to dokładnie jeden.
Tw. Jordana
Dla każdego drzewa T centrum T składa się z jednego wierzchołka, lub z dwóch wierzchołków sąsiadujących ze sobą.
Grafy dwudzielne
Def. Graf dwudzielny
Def. Graf pełny dwudzielny - dwudzielny i ...
fanatyczkaVampir