Matematyka dyskretna

Co nazywamy drzewem?

Drzewem nazywamy graf spójny i acykliczny.

Jakie grafy mają drzewo spinające?

Każdy graf spójny ma drzewo spinające.

Podaj warunek wystarczający na to, aby graf nieskierowany miał cykl Eulera.

Warunkiem koniecznym i wystarczającym na to by spójny graf nieskierowany miał cykl Eulera jest parzystość stopni wszystkich wierzchołków.

Co nazywamy grafem spójnym?

Graf którego każdy wierzchołek jest osiągalny z każdego innego nazywamy grafem spójnym.

Podaj warunek na to, by graf miał cykl Hamiltona.

Grafem hamiltonowskim w szczególności jest każdy graf pełny, posiadający przynajmniej 3 wierzchołki oraz opisujący wielościan foremny.

Podaj warunek na to, aby krawędź e była częścią cyklu.

Jeśli e jest krawędzią w zamkniętej drodze prostej w grafie G to e należy do jakiegoś cyklu.

Co nazywamy izomorfizmem grafu G na graf H?

Grafy G i H nazywamy izomorficznymi, jeżeli istnieje bijekcja zbioru wierzchołków grafu G na zbiór wierzchołków grafu H, która zachowuje strukturę grafu (krawędzie). Intuicyjnie oznacza to, że grafy G i H są tym samym grafem, jedynie poddanym jakiejś permutacji wierzchołków.

Podaj warunek na to, aby graf bez pętli i krawędzi wielokrotnych, mający n wierzchołków, był drzewem.

Graf bez pętli i krawędzi wielokrotnych (graf prosty) jest drzewem jedynie wtedy gdy spełniony jest jeden z warunków (podane niżej warunki są równoważne): • Każde dwa wierzchołki G są połączone dokładnie jedną drogą prostą. • G jest spójny, ale przestaje być spójny po usunięciu jakiejkolwiek krawędzi • G jest acykliczny, ale przestaje być acykliczny po dodaniu jakiejkolwiek krawędzi

Jak wiążą się ze sobą stopnie wierzchołków grafu i liczba krawędzi? Objaśnij użyte symbole.

Suma stopni wierzchołków grafu jest dwa razy większa od liczby krawędzi. To znaczy € deg(v) = 2 E(G) v∈V (G) Σ.

Podaj twierdzenie Eulera dla grafów skierowanych.

Graf skierowany posiada drogę Eulera, gdy wszystkie wierzchołki z wyjątkiem dwóch mają takie same stopnie wychodzące i wchodzące, w jednym z tych dwóch wierzchołków stopień wychodzący jest o 1 większy niż wchodzący a w drugim odwrotnie. Inaczej skierowany graf eulerowski definiowany jest jako graf silnie spójny, w którym dla każdego wierzchołka grafu liczba krawędzi wchodzących jest równa ilości krawędzi wychodzących.