Matematyka dyskretna

 0    10 fiszek    pawelsna
ściągnij mp3 drukuj graj sprawdź się
 
Pytanie język polski
Odpowiedź język polski

Co nazywamy drzewem?
rozpocznij naukę
Drzewem nazywamy graf spójny i acykliczny.

Jakie grafy mają drzewo spinające?
rozpocznij naukę
Każdy graf spójny ma drzewo spinające.

Podaj warunek wystarczający na to, aby graf nieskierowany miał cykl Eulera.
rozpocznij naukę
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?
rozpocznij naukę
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.
rozpocznij naukę
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.
rozpocznij naukę
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?
rozpocznij naukę
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.
rozpocznij naukę
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.
rozpocznij naukę
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.
rozpocznij naukę
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.


Musisz się zalogować, by móc napisać komentarz.