1. Co nazywamy drzewem?
Drzewem nazywamy graf spójny i acykliczny.
2. Jakie grafy mają drzewo spinające?
Każdy graf spójny ma drzewo spinające.
3. 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.
4. Co nazywamy grafem spójnym?
Graf którego każdy wierzchołek jest osiągalny z każdego innego nazywamy grafem
spójnym.
5. Podaj warunek na to, by graf miał cykl Hamiltona.
Tw1: Graf prosty o n≥3 wierzchołkach, taki, że dla każdego wierzchołka V deg(V)≥n/2 ma cykl Hamiltona.
Tw2: Jeżeli graf prosty o n≥3 wierzchołkach ma co najmniej ½(n-1)(n-2)+2 krawędzi, to ma cykl Hamiltona.
Tw3: Jeżeli w grafie prostym o n≥3 wierzchołkach dla dwóch dowolnych wierzchołków U i V nie połączonych krawędzią deg(U)+deg(V)≥n, to graf ma cykl Hamiltona.
6. Podaj warunek na to, aby krawędź e była częścią cyklu.
G- graf spójny, e-krawędź grafu G. Następujące warunki są równoważne:
· graf G\{e} jest spójny
· e jest krawędzią w pewnym cyklu w G
· e jest krawędzią w pewnej zamkniętej drodze prostej w G.
7. Co nazywamy izomorfizmem grafu G na graf H?
Grafy proste G i H są izomorficzne, jeżeli istnieje bijekcja alfa:V(G)->V(H) taka, że (alfa(U), alfa(V) )należy do E(H) ó(U,V) należy do E(G).
8. Podaj warunek na to, aby graf bez pętli i krawędzi wielokrotnych, mający n
wierzchołków, był drzewem.
Tw: Niech graf prosty o n wierzchołkach. Następujące warunki są równoważne (jednocześnie konieczne i wystarczające):
· G jest drzewem
· G jest spójny i ma n-1 krawędzi
· G jest acykliczny i ma n-1 krawędzi.
9. 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) Deg(V)- stopień wierzchołka V, |E(G)|- liczba krawędzi grafu G
V należy do V (G)
11. Co nazywamy drzewem spinającym?
Niech G - graf spójny. Najmniejszy podgraf spójny tego grafu zawierający wszystkie
wierzchołki nazywamy drzewem spinającym grafu G.
14. Co nazywamy cyklem?
Cyklem nazywamy drogę prostą zamkniętą o długości ≥1, której wszystkie wierzchołki są
różne.
15. Podaj warunek na to, by graf dwudzielny miał cykl Hamiltona.
Graf dwudzielny ma cykl Hamiltona wtedy i tylko wtedy, gdy
V1(G) = V2 (G) .
16. Kiedy mówimy, że wierzchołek V jest osiągalny z wierzchołka U?
Jeżeli w grafie istnieje droga o początku w u i końcu w v.
19. Co wynika z tego, że istnieje droga z wierzchołka U do wierzchołka V?
Jeżeli w grafie istnieje droga z U do V, to istnieje droga prosta acykliczna z U do V.
21. Podaj warunek wystarczający na istnienie w grafie cyklu Hamiltona.
G niema pętli i krawędzi wielokrotnych |V(G)|=n>3 dla każdego należącego do V (G)deg(V ) ≥ n/2
22. Co to jest drzewo spinające grafu? Kiedy istnieje?
Najmniejszy podgraf spójny grafu G zawierający wszystkie wierzchołki G nazywamy
drzewem spinającym grafu G. Każdy graf spójny ma drzewo spinające
23. Podaj warunek na to, aby graf acykliczny był drzewem. Jaki to warunek?
Warunek konieczny i wystarczający - G jest acykliczny, ale przestaje być acykliczny po dodaniu jakiejkolwiek krawędzi.
26. Co to jest cykl?
Każda droga prosta zamknięta o długości >1, w której wszystkie wierzchołki są różne nazywamy cyklem.
27. Przy jakich założeniach wiemy, że w grafie G istnieje droga prosta acykliczna z
wierzchołka U do wierzchołka V?
Istnieje droga z U do V.
29. Podaj warunek wystarczający na to, by graf miał cykl Eulera.
Graf spójny mający wszystkie wierzchołki stopnia parzystego ma cykl Eulera.
32. Co wiemy o grafie dwudzielnym, jeśli ma on drogę Hamiltona?
V1(G),V2(G) różnią się o 1. (15)
33. Kiedy graf nazywamy pełnym?
Graf prosty o n wierzchołkach, w którym każde 2 wierzchołki są połączone krawędzią
nazywamy pełnym.
34. Podaj warunki na to, by krawędź e należała do jakiegoś cyklu. Co to za warunki:
konieczne czy wystarczające?
Jeśli e jest krawędzią w zamkniętej drodze prostej w grafie G to e należy do jakiegoś
cyklu. (6)
35. Jaki warunek musi spełniać graf mający cykl Eulera?
Warunek konieczny - ma wszystkie wierzchołki stopnia parzystego.
36. Co nazywamy drzewem binarnym?
Drzewo z wyróżnionym korzeniem jest drzewem binarnym wtedy, gdy każdy węzeł ma
co najwyżej dwoje dzieci.
37. Co wiemy o grafie dwudzielnym, jeśli ma on cykl Hamiltona? (15)
39. Co nazywamy wysokością drzewa z wyróżnionym korzeniem?
Wysokością drzewa jest największy poziom istniejący w drzewie.
40. Kiedy mówimy, że wierzchołek V jest osiągalny z wierzchołka U?
Jeżeli w grafie istnieje droga o początku w U i końcu w V.
41. Przy jakich założeniach istnieje co najwyżej jedna droga prosta łącząca dwa wierzchołki
grafu?
Jeżeli u i v są różnymi wierzchołkami grafu acyklicznego g.
42. Ile krawędzi ma drzewo o n wierzchołkach?
Drzewo mające n wierzchołków ma dokładnie n-1 krawędzi.
43. Co to jest cykl Hamiltona?
Drogą prostą zamkniętą przechodzącą przez każdy wierzchołek grafu dokładnie 1 raz nazywamy cyklem Hamiltona.
46. Podaj związek między stopniami wierzchołków w grafie a liczbą krawędzi.
Suma stopni wierzchołków grafu jest 2 razy większa niż liczba krawędzi.
47. Co to jest graf dwudzielny?
Graf G nazywamy grafem dwudzielnym, jeżeli V(G)=V1 suma mnogościowa V2 , V1(G)i(część wspólna)V2różne od 0 oraz dla każdego e=(U,V) nażelżące do E(G) U należy do V1 (G), V należy do V2(G) lub odwrotnie.
48. Podaj warunki na to, by graf był drzewem. Co to za warunki: konieczne czy
wystarczające? (8) + są to warunki konieczne i wystarczające
- Drzewem nazywamy graf spójny i acykliczny
- Drzewo musi być grafem prostym
51. Podaj warunek na to, by graf miał drogę Eulera, ale nie miał cyklu Eulera.
Graf musi być spójny i musi mieć 2 wierzchołki stopnia nieparzystego, a pozostałe stopnia parzystego.
53. Podaj warunek na to, aby istniał cykl, do którego należy wierzchołek V.
V należy do cyklu, wtedy i tylko wtedy gdy V należy do zamkniętej drogi prostej.
54. Co nazywamy drogą w grafie skierowanym, a co długością drogi?
Drogę w grafie g nazywamy ciąg jego krawędzi (e1,…,en) taki, że dla każdego i=1,…,n-1
początek ei+1 = koniec ei
Długość drogi to ilość krawędzi wchodzących w jej skład.
55. Kiedy graf nazywamy spójnym?
56. Co to jest droga Hamiltona w grafie?
Drogę prostą w grafie, która przez każdy wierzchołek grafu przechodzi dokładnie jeden
raz nazywamy drogą Hamiltona.
57. Podaj warunek na to, by droga w grafie była acykliczna.
Droga (V0,V1,...Vk) nie jest cyklem jeżeli Vi≠Vj i≠j i,j{0,1,...,k}, droga musi być prosta.
59. Co to jest stopień wierzchołka grafu?
Stopniem wierzchołka V nazywamy liczbę wierzchołków sąsiednich do wierzchołka V w
grafie G .
61. Napisz prawo kontrapozycji w rachunku zdań.
(pðq) ó (~qð~p)
62. Podaj twierdzenie o przedstawieniu formuły rachunku zdań w postaci koniunkcyjno –
alternatywnej.
Każdą formułę rachunku zdań można przedstawić w postaci koniunkcyjno-alternatywnej.
63. Napisz prawa de Morgana w algebrze Boole’a.
∀ x, y ∈ X (x ∨ y) ‘= x’ ∧ y’
∀ x, y∈ X (x ∧ y)’ = x’ ∨ y’
64. Co nazywamy funkcją logiczną?
P - zdanie logiczne
p(x) - x U –funkcja logiczna
Funkcją zdaniową nazywamy wyrażenie zawierające zmienne, które stają się zdaniem gdy
za te zmienne podstawimy konkretne wartości.
65. Co to jest formuła w postaci alternatywno – koniunkcyjnej?
Formułę postaci ( )v( )v…v( ) gdzie w nawiasach są koniunkcje elementarne.
66. Napisz uogólnione prawa de Morgana w rachunku predykatów.
67. Kiedy zbiory nazywamy równolicznymi?
Mówimy, że zbiory A i B są równoliczne jeżeli istnieje bijekcja f:A B.
68. Narysuj układ bramek logicznych, który na wyjściu będzie dawał (~p∧q)∨(~q∧r)
69. Jak brzmi 1 Reguła Podstawiania?
Jeżeli zdanie złożone P jest tautologią i jeżeli w tym zdaniu zmienną zdaniową P
zastąpimy inną zmienną zdaniową Q, to zmienione zdanie P' będzie tautologią.
70. Udowodnij za pomocą tablicy wartości logicznych, że (p∨q)∧~(p∧q) ó (p q)
72. Napisz prawa rozdzielności w algebrze Boole’a.
∀ x, y, z ∈ X x ∨ (y ∧ z) = (x ∧ z)∨ (x ∧ y)
∀ x, y, z ∈ ...
kopecki17