* graf prosty - niepusty zbiór skoczony V(G) i skończony zbiór V(E). Krawedz {v,w} łączy wierzchołki v i w, w skrócie zapisywana jako vw. Istnieje w nim co najwyżej jedna krawędź łącząca daną parę wierzchołków, nie ma pętli ani krawędzi wielokrotnych,
* multigraf - może posiadać krawędzie wielokrotne
* hipergraf - hiperkrawędzie mogą stanowić krotki wierzchołków a nie tylko pary, relacje o wyższej arności niż 2
* graf ogólny - mogą istnieć więcej niż 1 krawędź dla danej pary wierzchołków
* V(G) - zbiór wierzchołków
* V(E) - rodzina krawędzi
* IZOMORFIZM - grafy G1 i G2 są izomorficzne, jeżeli istnieje wzajemna jednoznaczna odpowiednioś między wierzchołkami G1 i G2, taka że liczba krawędzi łącząca każdą parę wierzchołki grafu G1 jest równa liczbie krawędzi łączących odpowiadające wierzchołki w G2.
* nie jest znany efektywny algorytm sprawdzający czy grafy są izomorficzne (są znane hiperwielomianowe)
* SPÓJNOŚĆ - graf jest spójny, jeżeli nie możemy przedstawić go za pomocą sumy dwóch grafów; od każdego wierzchołka istnieje ścieżka do każdego innego wierzchołka
* graf niespójny - można go przedstawić w postaci sumy grafów spójnych, czyli jego składowych
* silna spójność - dla każdej uporządkowanej pary różnych wierzchołków istnieje droga skierowana z pierwszego do drugiego
* składowe grafu - grafy spójne za pomocą sumy których można przedstawić graf docelowy; maksymalny podgraf grafu, który jest spójny
* składowa silnie spójna - maksymalny podgraf silnie spójny
* składowa słabo spójna - maksymalny podgraf spójny
* sąsiedztwo wierzchołków - wierzchołki v i w są sąsiednie jeżeli łączy je krawędź
* incydencja - jeżeli v i w są połączone krawędzią, to mówi się, że te wierzchołki sa z nią incydentne
* sąsiedztwo krawędzi - mają wspólny wierzchołek
* stopień wierzchołka deg(v) - liczba krawędzi z nim incydentnych
* minimalny - δ_min(G)
* maksymalny - Δ(G)
* wierzchołek izolowany - wierzchołek stopnia 0
* wierzchołek końcowy - wierzchołek stopnia 1
* ciąg stopni grafu - ciąg stopni wierzchołków w kolejności niemalejącej, uwzględnione są w nim powtórzenia
* graf pusty - zbiór krawędzi jest zbiorem pustym, regularny stopnia 0
* graf pełny - każda para wierzchołków jest połączona krawędzią. Graf K_n ma n(n-1)/2 krawędzi, graf pełny K_n jest grafem regularnym stopnia n-1
* grafy cykliczne C_n - graf spójny, regularny stopnia 2
* graf liniowy P_n - graf uzyskany przez usunięcie jednej krawędzi z C_n
* graf kołowy W_n - pozyskany z grafu C_n-1 przy czym dodaje się 1 wierzchołek połączony z każdym z pozostałych wierzchołków
* grafy regularne - każdy wierzchołek ma ten sam stopień, jeśli każdy ma stopień r to jest to gra r-regularny,
* grafy kubiczne - grafy regularne 3 stopnia, grafy 3-regularne,
* graf Petersena:
* 
* grafy platońskie - powstałe z wierzchołków i krawędzi wielościanów foremnych (4, 6, 8, 12, 20 ściany)
* 
* grafy dwudzielne - grafy w których zbiór wierzchołków V może zostać podzielony na zbiór A i B tak, aby każda krawędź łączyła wierz. z A z B.
* graf pełny dwudzuelny K_r,s - dwudzielny, tylko każda krawędź z A jest połączona z każdą z B i vice versa.
* kostki - k-kostką Q_k nazwiemy graf którego wierzchołki odpowiadają ciągom (a1, a2, ... ak) takim, że każdy wyraz ai jest równy 0 lub 1 i krawędzie łączą wierzchołki różniące się max jednym wyrazem.
* kostka stopnia k Q_k ma dokładnie 2^k wierzchołków i k*2^(k-1) krawędzi, jest grafem regularnym stopnia k
* dopełnienie grafu \[ z kreska u gory \] - ten sam zbiór wierzchołków co G ale wierzchołki sąsiednie witwg nie są sąsiednie w G
* podgraf - podgrafem grafu G nazywamy graf który ma wszystkie wierzchołki grafu G i podzbiór jego krawędzi.
* podgraf grafu G indukowany przez zbiór V' (podzbiór V) to podgraf zawierający V' oraz każdą krawędź z nim incydentną
* ściągnięcie krawędzi G\e - polega na usunięciu krawędzi i połączeniu jej wierzchołków końcowych w jeden wierzchołek
* łuk - krawędź skierowana

# Drogi i cykle
* trasa - skończony ciąg postaci v0v1,v1v2,v2v3,...vm-1vm w którym każde dwie kolejne krawędzie są albo sąsiednie albo identyczne
* wierzchołki początkowe i końcowe to wtedy v0 i vm
* długośc trasy - liczba krawędzi
* ścieżka - trasa z różnymi krawędziami
* droga - ścieżka z różnymi wierzchołkami (also trasa z różnymi krawędziami i wierzchołkami)
* droga zamknięta - droga w której v0 = vm, czyli wierzchołek początkowy = w. końcowy
* cykl - droga zamknięta zawierająca przynajmniej 1 krawędź
* obwód grafu - długość najkrótszego cyklu elementarnego w grafie (Q_3 ma obwód 4)
* 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 nie jest już zbiorem rozspajającym
* spójność krawędziowa λ(G) - liczba krawędzi należących do najmniej licznego rozcięcia grafu, najmniejsza liczba krawędzi których usunięcie rozspoi graf
* k-spójność krawędziowa - graf jest k-spójny krawędziowo jeżeli λ(G) >= k, jeśli trzeba 2 krawędzi, żeby rozspoić to jest on 1 i 2 spójny-krwędziowo ale nie jest 3 spójny-krawędziowo (DUMB)
* zbiór rozdzielający - zbiór wierzchołków których usunięcie spowoduje, że graf ten przestaje być spójny
* wierzchołek rozcinający lub punkt artykulacji (jednoelementowy zbiór rozdzielający)
* spójnośc wierzchołkowa κ(G) - jeśli graf jest spójny i nie jest pełny, to κ(G) to liczba elementów najmniej licznego zbioru rozdzielającego, czyli najmniejsza liczba wierzchołków której usunięcie rozspoi graf.
* k-spójność - jeśli κ(G) >= k to jest on k spójny. analogicznie co wyżej
* most - jednokrawędziowe rozcięcie
* blok - maksymalny podgraf grafu niezawierający punktów artykulacji dla tego pografu
* odległość między v i w w grafie to długość najkrótszej ścieżki łączące v i w
* średnica - max dist między wierzchołkami w grafie
* ekscentryczność wierzchołka - max dist od innego wierzchołka
* promień grafu - minimalna ekscentryczność wierzchołka
* wierzchołek centralny - wierzchołek o minimalnej ekscentryczności
* centrum grafu - graf indukowany na zbiorze wierzchołków centralnych grafu G
* μ(s, v) - długość najkrótszej ścieżki (jeśli istnieje)
* Algorytm Kruskala - służy do znajdowania minimalnego drzewa spinającego
* Algorytm Dijkstry - znajdowanie najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi.

## Grafy eulerowskie
* cykl Eulera - ścieżka zamknięta zawierająca każda krawędź G.
* graf eulerowski - graf zawierający ściezkę Eulera
* ścieżka eulera - ścieżka zawierająca każdy wierzchołek grafu G
* graf półeulerowski - istnieje w nim ścieżka zawierająca każdą krawędź G.

## Grafy hamiltonowskie
* cykl Hamiltona - zamknięta ścieżka przechodząca dokładnie jeden raz przez każdy wierzchołek grafu
* graf hamiltonowski - posiada cykl hamiltona
* graf półhamiltonowski - istnieje droga przechodząca dokładnie jeden raz przez ażdy wierzchołek,

# Rozdział 4 - drzewa

* las - graf niezawierający cykli
* drzewo - las spójny
* drzewa i lasy są grafami prostymi
* drzewo spinające bądź rozpinające graf G - podzbiór grafu G będący drzewem,
* rząd cykliczności (liczba cyklomatyczna) γ(G) - liczba krawędzi usuniętych w czasie pozyskiwania drzewa spinającego
* rząd rozcięcia (rząd spójności) ξ(G) - liczba krawędzi w lesie spinających.
* ξ(G) + γ(G) = |E(G)|
* dopełnienie lasu spinającego T grafu G - graf otrzymany z G przez usunięcie krawędzi należących do T.
* fundamentalny zbiór cykli związany z T - zbiór cykli utworzonych przez dołączenie do T oddzielnie każdej krawędzi grafu G, nienależącej do T
* fundamentalny zbiór rozcięć grafu - zbiór wszystkich krawędzi grafu G łączących wierzchołki zbioru V1 z wierzchołkami V2 jest rozcięciem w grafie G a zbiór wszystkich rozcięć nazywamy fundamentalnym zbiorem rozcięć grafu G
* przestrzeń krawędzi W_e(G) - zbiór wszystkich podzbiorów E(G)
* operacja sumy prostej E_1 + E_2 = (E1\E2) U (E2\E1)
* W_C(G) - cykle uogólnione - zbiory krawędzi cykli G i sum cykli kraawędizowo rozłacznych
* W grafie G istnieje dokładnie 2^(γ(G)) różnych cykli uogólnionych
* w grafie G istnieje dokładnie 2^(ξ(G)) różnych podgrafów, z których każdy jest rozcięciem lub sumą rozcięć krawędziowo rozłącznych
* Minimalne drzewo spinające MST - drzewo zawierające wszystkie wierzchołki i podzbiór krawędzi oryginalnego grafu, przy czym suma wag krawędzi jest w nim minimalna
* drzewa etykietowane:
* wierzchołki mają etykiety będące kolejnymi dodatnimi N
* n^(n-2) ilość drzew etykietowanych o n wierzchołkach
* liczba Catalana bn - 1/(n+1) * dwumianNewtona(2n nad n) - liczba różnych drzew binarnych o n wierzchołkach
* **ZASTOSOWANIA**:
* informatyce (np. jako struktury danych)
* sztucznej inteligencji (np. drzewa decyzyjne, drzewa gier)
* eksploracji danych (np. kd-drzewa)
* przetwarzaniu j¦zyka naturalnego (np. drzewa parsowania)
* organizacji informacji (np. modele hierarchiczne, taksonomie)
* biologii (np. drzewa genealogiczne)
* teorii gier (np. zasada minimaksowa)
* w informatyce jako efektywne implementacje ważnych abstrakcyjnych struktur danych, np.:
* drzewo wyszukiwań binarnych (implementacja uporządkowanego słownika) (inne: AVL, B-drzewa, czerwono-czarne, itd.)
* kopiec binarny (implementacja kolejki priorytetowej)
* kopiec dwumianowy (implementacja złączalnej kolejki priorytetowej) (inne: kopiec Fibonacciego, drzewa van Emde Boas, itd.)
* drzewo Huffmana (zwarta reprezentacja kodu prefiksowego)
* drzewo sufiksowe (zwarta reprezentacja przeszukiwanego ciągu symboli)* ZLICZANIE:
* liczbą Catalana (wyżej)

# Planarność
* Graf planarny to taki graf, który można narysować na płaszczyźnie bez przecinających się krawędzi.
* Grafy K5 i K3,3 nie są planarne (tzw. grafy Kuratowskiego).
* Każdy podgraf grafu planarnego jest planarny.
* Graf zawierający jako podgraf graf nieplanarny sam jest nieplanarny.
* Warunek wystarczający nieplanarności - Jeśli graf zawiera graf Kuratowskiego jako podgraf, to jest nieplanarny.
* Dwa grafy są homeomorficzne ⇔ oba można uzyskać z pewnego grafu poprzez wstawianie wierzchołków stopnia 2 wewnątrz ich krawędzi.
* Graf jest planarny ⇔ nie zawiera podgrafu homeomorficznego z K5 ani z K3,3.
* Liczba przecinających się krawędzi cr(G) grafu G to najmniejsza możliwa liczba przecinających się krawędzi w dowolnym rysunku grafu G na płaszczyźnie. - graf Petersena i K4,3 mają liczbę przecinających się krawędzi równą 2.
* Graf nazywamy zewnętrznie planarnym ⇔ można go tak narysować na płaszczyźnie bez przecinających się krawędzi, że wszystkie wierzchołki leżą na zewnętrznym obrzeżu. Graf jest zewnętrznie planarny ⇔ nie zawiera grafu homeomorficznego z K4 ani K2,3 ani izomorficznego do żadnego z nich.
* Jeśli G jest dowolnym rysunkiem płaskim spójnego grafu planarnego, to zachodzi następujący wzór: n − m + f = 2 gdzie: f to liczba ścian w tym rysunku, m jest liczbą krawędzi, a n liczba wierzchołków.
* Jeśli G jest spójnym, prostym grafem planarnym mającym n ≥ 3 wierzchołków, to:
* Jego liczba krawędzi m spełnia: m ≤ 3n − 6.
* Jeśli ponadto G nie zawiera trójkątów C3, to zachodzi: m ≤ 2n − 4.
* Każdy graf planarny prosty zawiera co najmniej jeden wierzchołek stopnia mniejszego niż 5.
* Grubość t(G) grafu G to najmniejsza liczba "przezroczystych warstw" zawierających rysunki płaskie podgrafów G, które "sklejone" dałyby graf G. Jest to inna miara "nieplanarności" grafu.
* Genus grafu to najniższy możliwy genus powierzchni, na której można dany graf narysować bez przecinających się krawędzi.

## reprezentacje grafów
### macierz sąsiedztwa Θ(n^2)
* kolumny, wiersze - wierzchołki, wartości to ilość krawędzi łączących daną parę
* suma dowolnego wiersza lub kolumny równa się stopniowi wierzchołka
### macierz incydencji Θ(n*m)
* ↓kolumny - krawędzie,
* →wiersze - wierzchołki e
* 
* suma dowolnego wiersza wskazuje na stopień wierzchołka
* suma dowolnej kolumny zawsze == 2 ( no bo krawędź ma 2 końce)
### lista sąsiedztwa Θ(n+m)
* listy odpowiadające poszczególnym wierzchołkom, lista rozpoczyna się od etykiety wierzchołka a potem podana jest lista wierzchołków sąsiednich ( w skierowanych są to wychodzące z danego wierzchołka)
### lista krawędzi
* każda krawędź (v,w) w oddzielnej linii, dobra do grafów zwiększających się dynamicznie
### reprezentacja obiektowa
* każdy wierzchołek i krawędź to obiekty, istnieją dowiązania przez referencje
### gd0
* niskopoziomowy format binarny, połączona lista ciągów identyfikatorów całkowitoliczbowych, ciągi postci id_i, deg_i, n_i,1...n_i,deg_i - id wierzchołka, jego stopień wyjściowy, ciąg id jego sąsiadów)

# Twierdzenia
### Jeśli graf G jest grafem dwudzielnym to każdy cykl w G ma długość parzystą
### Jeśłi w grafie G każdy wierzchołek ma stopień równy co najmniej 2 to graf zawiera cykl.
### Graf spójny G jest grafem eulerowskim wtedy i tylko wtedy gdy stopień każdego wierzchołka grafu G jest liczbą parzystą.
### Graf spójny jest grafem eulerowskim wtedy i tylko wtedy gdy zbiór jego krawędzi można podzielić na rozłączne cykle
### Graf spójny jest grafem półeulerowskim wtedy i tylko wtedy gdy ma dokładnie dwa wierzchołki nieparzystych stopni.
### Jeśli graf prosty G ma n wierzchołków (gdzie n>=3) oraz deg(v) + deg(w) >= n dla każdej pary wierzchołków niesąsiednich v i w to graf G jest hamiltonowski.
### Niech T będzie grafem mającym n wierzchołków. Wtedy równoważne są twierdzenia:
* T jest drzewem,
* T nie zawiera cykli i ma n-1 krawędzi,
* T jest grafem spójnym i ma n-1 krawędzi,
* T jest grafem spójnym i każda krawędź jest mostem,
* każde dwa wierzchołki T połączone są dokładnie 1 drogą,
* T nie zawiera cykli ale po dodaniu dowolnej nowej krawędzi otrzymamy graf mający dokładnie 1 cykl.

### Jeśli graf jest lasem, który ma n wierzchołków i k składowych, to G ma n-k krawędzi.
### Jeśli T jest lasem spinającym grafu T to każde rozcięcie grafu G ma wspólną krawędź z T a każdy cykl w grafie G ma wspólną krawędź z dopełnieniem T.
### Istnieje n^(n-2) różnych drzew oznakowanych mających n wierzchołków.
### Graf K_n ma n^(n-2) drzew spinających
### graf prosty o n wierzchołkach i k składowych ma m krawędzi, gdzie n-k <= m <= (n-k)(n-k-1)/2 -> jeśli graf prosty o n wierzchołkach ma więcej niż (n-1)(n-2)/2 krawędzi to jest spójny
### Jeśli w grafie prostym G minimalny stopień wierzchołka to δ > 1, to graf zawiera cykl o długości conajmniej δ+1
### Genus grafu G jest nie większy od jego liczby przecinających się krawędzi cr(G).
### Jeśli G jest spójnym grafem o genusie g, to zachodzi: n − m + f = 2 − 2g. f to liczba ±cian w tym rysunku, m jest liczbą krawędzi, a n liczba wierzchołków. Liczba g to liczeność genusu jeśli jest homeomorficzna ze sferą z "doklejonymi" g uchwytami.

## lemat o uściskach dłoni
* W każdym grafie suma stopni wszystkich wierzchołków jest liczbą parzystą, równej podwojonej liczbie krawędzi.
* W dowolnym grafie liczba wierzchołków o nieparzystych stopniach jest parzysta.

## Algorytmy

### znajdywanie punktów artykulacji
1. Przejdź graf w głąb (DFS) rozpoczynając od dowolnego wierzchołka jako korzenia.
2. Przydziel każdemu odwiedzonemu wierzchołkowi czas wejścia (numeracja odwiedzonych wierzchołków).
3. Dla każdego odwiedzonego wierzchołka v, zapisz najmniejszy numer czasu wejścia (low[v]) spośród numerów czasu wejścia wszystkich sąsiadów wierzchołka v (nie wchodzących wstecz do przodka).
4. Jeśli wierzchołek v jest korzeniem drzewa DFS i ma więcej niż jedno dziecko, oznacz v jako punkt artykulacji.
5. Dla każdego wierzchołka v różnego od korzenia drzewa DFS, jeśli dla dowolnego sąsiada u wierzchołka v, low[u] >= numer czasu wejścia[v], oznacz v jako punkt artykulacji.
6. Powtarzaj kroki 3-5 dla każdego nieodwiedzonego sąsiada v, aby przejrzeć cały graf.
Po wykonaniu powyższego algorytmu, wierzchołki oznaczone jako punkty artykulacji są tymi, których usunięcie powoduje podział grafu na więcej składowych spójnych niż przed ich usunięciem.

### obliczanie spójności wierzchołkowej
1. Dla każdego wierzchołka v w grafie:
1. Usuń wierzchołek v z grafu.
2. Wykonaj przeszukiwanie grafu w głąb (DFS) lub przeszukiwanie wszerz (BFS) z dowolnego pozostałego wierzchołka.
3. Sprawdź, czy wszystkie wierzchołki grafu zostały odwiedzone. Jeśli tak, to oznacza, że usunięcie wierzchołka v rozspójniło graf na więcej niż jedną składową spójną.
4. Przywróć wierzchołek v do grafu.
2. Zapisz liczbę wierzchołków, które muszą zostać usunięte, aby rozspójnić graf na więcej niż jedną składową spójną. Ta liczba jest minimalną spójnością wierzchołkową grafu.
Ten prosty algorytm polega na iteracyjnym usuwaniu każdego wierzchołka i sprawdzaniu, czy graf pozostaje spójny. Jeśli usunięcie wierzchołka powoduje rozspójnienie grafu, to ten wierzchołek jest klasyfikowany jako punkt artykulacji i liczba usuniętych wierzchołków jest minimalną spójnością wierzchołkową.

### obliczanie spójności krawędziowej
1. Dla każdej krawędzi e w grafie:
1. Usuń krawędź e z grafu.
2. Wykonaj przeszukiwanie grafu w głąb (DFS) lub przeszukiwanie wszerz (BFS) z dowolnego wierzchołka.
3. Sprawdź, czy wszystkie wierzchołki grafu zostały odwiedzone. Jeśli tak, to oznacza, że usunięcie krawędzi e rozspójniło graf na więcej niż jedną składową spójną.
4. Przywróć krawędź e do grafu.
2. Zapisz liczbę krawędzi, które muszą zostać usunięte, aby rozspójnić graf na więcej niż jedną składową spójną. Ta liczba jest minimalną spójnością krawędziową grafu.
Ten prosty algorytm polega na iteracyjnym usuwaniu każdej krawędzi i sprawdzaniu, czy graf pozostaje spójny. Jeśli usunięcie krawędzi powoduje rozspójnienie grafu, to ta krawędź jest klasyfikowana jako most lub krawędź artykulacyjna, a liczba usuniętych krawędzi jest minimalną spójnością krawędziową.

### BFS
* Przeszukiwanie wszerz (ang. breadth-first search, **BFS**) – jeden z najprostszych algorytmów przeszukiwania grafu. Przechodzenie grafu rozpoczyna się od zadanego wierzchołka s i polega na odwiedzeniu wszystkich osiągalnych z niego wierzchołków. Wynikiem działania algorytmu jest drzewo przeszukiwania wszerz o korzeniu w s, zawierające wszystkie wierzchołki osiągalne z s.
* używa kolejki
* zastosowania:
* obliczanie składowych spójnych (stanowi ją każde drzewo)
* obliczanie odległości od wierzchołka
* obliczanie domknięcia przechodniego relacji (nxBFS)
* czas odwiedzenia - czas kiedy pierwszy raz wbijamy na wierzchołek, czyli step z licznika globalnego time
* czas przetworzenia/zakończenia - czas w którym zostaje pokolorowany na czarno (wtdy gdy do niego wracamy po przejściu przez jego sąsiadów albo od razu jeśli ich nie ma)
*
### DFS
* Przeszukiwanie w głąb (ang. Depth-first search, w skrócie DFS) – algorytm przeszukiwania grafu. Przeszukiwanie w głąb polega na badaniu wszystkich krawędzi wychodzących z podanego wierzchołka.
* używa stosu
* zastosowania:
* testowanie acykliczności (nieistnienie krawędzi wstecz) - przechodzimy go algorytmem DFS. Jeśli w trakcie przechodzenia natrafimy na wierzchołek już odwiedzony, a nie jest to wierzchołek, z którego przyszliśmy, to graf jest cykliczny.
* sortownie topologiczne
* składowe silnie spójne
* znajdowanie puntków artykulacji
* znajdowanie mostów
* krawędź jest mostem <=> nie leży na żadnym cyklu
* rozkład grafu na bloki
* ZNAJDYWANIE MOSTÓW - kontraktacja podrgafu H - uczynienie z niego pojedynczego wierzchołka - przez kontraktację każdej składowej spójnej grafu G otrzymujemy drzewo H, którego krawędzie odpowiadają mostom grafu G. ALGORYTM STOPNIOWO PODDAJE KONTRAKTACJI CYKLE AŻ ZOStANĄ SAME MOSTY
* sortowanie topologiczne (skierowane)
* zastosować DFS,
* ustawić V od największego czasu zakończenia do najmniejsego
* znajdywanie skł. silnie spójnych
* oblicz DFSem czasy zakończenia
* odwróć kierunki krawędzi
* DFS na transponowanym grafie (zgodnie z malejącym czasem zakończenia z kr.1)
* otrzymane drzewa to składowe silnie spójne
* ścieżka DFS - fragment drzewa przeszukiwania DFS zbudowany do momentu gdy dany wierzchołek staje się czarny
* MST jako przybliżenie TSP:
* znaleźć dowolne drzewo rozpinające i zastąpić każdą krawędź parą krawędzi przeciwnych
* znaleźć cykl Eulera
* pominąć (stosując skróty) w tym cyklu wszystkie wierzchołki które występowałyby wielokrotnie
* jak wyznaczyć średnicę drzewa nieskierowanego:
- puszczamy BFSa z dowolnego wierzchołka, może to być root,
- po przejściu wybieramy wierzchołek najbardziej oddalony od początkowego, obieramy go jako nowy początkowy, puszczamy BFS jeszcze raz, największa znaleziona teraz odleglosc jest równa średnicy naszego grafu
* liniowy algorytm znajdowania w grafie nieskierowanym ścieżki, która przechodzi przez każdą krawędź dokładnie raz w każda stronę
* alg. ścieżki Eulera
- sprawdzanie czy graf nieskierowany jest dwudzielny:
1. Wybierz dowolny wierzchołek startowy i przypisz mu kolor 1.
2. Inicjalizuj kolejkę lub stos i dodaj do niej wybrany wierzchołek.
3. Dopóki kolejka/stos nie jest pusta, wykonuj następujące kroki:
4. Pobierz wierzchołek v z kolejki/stosu.
5. Przejdź przez wszystkich sąsiadów wierzchołka v.
6. Jeśli sąsiad nie ma przypisanego koloru, przypisz mu przeciwny kolor niż wierzchołka v i dodaj go do kolejki/stosu.
7. Jeśli sąsiad ma ten sam kolor co wierzchołek v, to graf nie jest dwudzielny.
8. Jeśli przejście zostało zakończone i żadne konflikty kolorów nie wystąpiły, to graf jest dwudzielny.
- mecz pomiędzy n szachistami, r par gra partie, każdy chce rozegrać mecze jednym kolorem, zaproponuj algorytm. czy jest to możliwe w czasie liniowym?
1. Sprawdź, czy wartość n jest podzielna przez 2. Jeśli nie, to nie jest możliwe, aby każdy gracz rozgrywał mecze jednym kolorem, ponieważ wtedy jeden gracz zostałby bez partnera
2. Przydziel każdemu szachistowi początkowo kolor A.
3. Utwórz dwie listy: listę szachistów z kolorem A (lista A) i listę szachistów z kolorem B (lista B).
4. Jeśli liczba szachistów w liście A jest równa liczbie szachistów w liście B, to przypisz graczom z listy A kolor B, a graczom z listy B kolor A.
5. Jeśli liczba szachistów w liście A jest różna od liczby szachistów w liście B, to nie jest możliwe, aby każdy gracz rozgrywał mecze jednym kolorem.
6. Jeśli liczba r (liczba par) jest mniejsza lub równa niż połowa liczby szachistów, to istnieje rozwiązanie. W przeciwnym razie nie jest możliwe, aby każdy gracz rozgrywał mecze jednym kolorem.
- wyznaczanie zbiorów cykli i rozcięć fundamentalnych danego grafu
- Niech L oznacza pewien las rozpinający grafu G,
- Gdy z lasu L usuniemy dowolną krawędź, to (w odpowiadającej jej składowej spójnej) powstają dwa rozłączne zbiory wierzchołków V1, V2. Zbiór wszystkich krawędzi G takich, że jeden koniec jest w V1 a drugi w V2 tworzy rozcięcie, które nazywamy rozcięciem fundamentalnym związanym z lasem L. Zbiór wszystkich takich rozcięć nazywamy zbiorem rozcięć fundamentalnych związanych z lasem L.

### Dwumian Newtona
### dane dokładne algosy

### kod Prufera
* Kod Prüfera to kod, który pozwala na zapisanie dowolnego drzewa w postaci skompresowanego ciągu. Po rozkodowaniu otrzymuje się dokładnie ten sam graf, który został zakodowany. Ciąg składa się z n-2 wartości, gdzie n to ilość węzłów w grafie. Drzewo musi mieć węzły ponumerowane kolejnymi liczbami np. od 0 do n - 1.
* Kodowanie drzewa polega na: wybraniu węzła, który jest liściem o najmniejszym, przypisanym numerze. Następnie należy do ciągu dopisać numer jego jedynego sąsiada, a jego samego usunąć. Proces ten należy powtarzać tak długo, aż zostaną dwa wierzchołki, które pomija się w zapisie ciągu. Uzyskany kod powinien składać się z n-2 wartości.
* W celu zakodowanie powyższego drzewo kolejno należy wybierać:
* Pozostały dwa ostatnie węzły, a więc algorytm został zakończony. W tym przypadku kod Prüfera to 1, 2, 1.

* Zakodowane drzewo niewiele mówi wprost o krawędziach grafu. W celu rozkodowania należy utworzyć sobie listę liczb od 1 do p + 2, gdzie p to długość kodu Prüfera. Jak można zauważyć p + 2 = n. Następnie należy wybrać z tej listy pierwszy element x, który nie występuje w kodzie oraz pierwszy element z kodu Prüfera y, a następnie na grafie utworzyć krawędź (x, y) i usunąć x z listy oraz pierwszy element z kodu. Na koniec na liście zostaną dwie wartości tj. ostatnia para wierzchołków do połączenia.
* W celu rozkodowania kodu Prüfera 1, 2, 1 tworzymy listę {0, 1, 2, 3, 4} i kolejno wybieramy:
* Z kodu Prüfera odczytane zostały kolejno krawędzie: {(0, 1), (3, 2), (2, 1), (1, 4)} czyli wszystkie krawędzie grafu pokazanego wyżej.