EGZ-LIC MIMUW MD

Matematyka dyskretna

17 flashcards · Computer Science · by Wojciech Rzepliński

1. Tw. Orego na istnieje cyklu Hamlitona

   Jeśli n=V(G)≥3n = V(G) \ge 3n=V(G)≥3 oraz forallv,w≠E(G)deg(v)+deg(w)≥nforall_{v,w \ne E(G)} deg(v) + deg(w) \ge nforallv,w=E(G)​deg(v)+deg(w)≥n

2. Tw. Cayleya, ile jest drzew n-wierzchołkowych

   nn−2n^{n-2}nn−2

3. Wzór Eulera do grafów planarnych

   n−m+f=2n - m + f = 2n−m+f=2 f - liczba ścian

4. Podaj ograniczenie na liczbę krawędzi w grafie planarnyn

   Jeżeli n≥3n \ge 3 n≥3 to m≤3n−6m \le 3n - 6m≤3n−6 Jeśli nie ma trójkątów w grafie, to m≤2n−4m \le 2n - 4m≤2n−4

5. Każdy graf nieplanarny jeśli zawiera co w sobie?

   Jeśli zawiera podgraf homeomorficzny z K3,3K_{3,3}K3,3​ oraz K5K_5K5​

6. Podaj zależność między grafem planarnym a maksymalnym stopniem:

   Każdy graf planarny zawiera wierzchołek stopnia ≤5\le 5≤5

7. Czym są grafy platońskie

   Regularne (taki sam stopień węzłów) taką samą liczbą krawędzi na każdej ścianie Jest ich 5

8. Czym jest liczba chromatyczna

   Najmniejsza liczba kolorów, aby pokolorować węzłów tak, aby dwa sąsiednie węzły miały inny kolor

9. Twierdzenie o 6 barwach

   Każdy graf planarny ma liczbę chromatyczną ≤6\le 6≤6 A nawet ≤5\le 5≤5 A nwet ≤4\le 4≤4 - tego się nie da poprawić

10. Twierdzenie Brooksa na liczbę chromatyczną za pomocą maksymalnego stopnia w grafie

    Jeśli G nie jest cyklem nieparzystej dł. ani kliką, to χ(G)≤Δ\chi(G) \le \Deltaχ(G)≤Δ ,gdzie Δ\Delta Δ to maksymalny stopień wierzchołka. Dla kliki oraz cyklu nieparzystej długośći to χ(G)=Δ+1\chi(G) = \Delta + 1χ(G)=Δ+1

11. Czym jest funkcja chromatyczna

    fG(t)f_G(t) fG​(t) to liczba pokolorwań grafu G za pomocą ttt kolorów.

12. Twierdzenie Vizinga (kolorowanie krawędziowe)

    χe(G)\chi_e(G) χe​(G) to najmniejsze kkk dla którego istnieje k-kolorowanie krawędziowe. Banalne: χe(G)≥Δ(G)\chi_e(G) \ge \Delta(G)χe​(G)≥Δ(G) Zaskakujące (Vizing): χe(G)≤Δ(G)+1\chi_e(G) \le \Delta(G) + 1χe​(G)≤Δ(G)+1

13. System różnych reprezentantów

    Wybranie po jednym elemencie z każdego zbioru, aby wszystkie elementy były różne. Można zamodelować grafem dwudzielnym. Po lewej są zbiory, a po prawej elementy, a krawędzie łączą zbiór z elementem który ma.

14. Tw. Halla

    Idealne skojarzenie w grafie dwudzielnym (SSR) istnieje wtedy i tylko wtedy, gdy dla każdego podzbioru elementów po lewej stronie sumaryczna liczba ich sąsiadów jest większa niż wielkość tego podzbioru

15. Czy graf regularny dwudzielny ma idealne skojarzenie?

    Tak, bo warunek Halla.

16. Kiedy dwa podziały A i B mają wspólny SSR?

    Wspólny SSR to taki wybór reprezentantów, że reprezentant zbioru AiA_iAi​ jest również reprezentantem zbioru Bσ(i)B_{\sigma(i)}Bσ(i)​ dla pewnej permutacji σ\sigmaσ . Istnieje, jeśli A i B są podziałami zbioru na bloki i każdych k bloków z A przecina łącznie conajmniej k bloków z B.

17. C(1−λx)k\frac{C}{(1 - \lambda x)^k}(1−λx)kC​ =?

    ∑n≥0C(n+k−1k−1)λnxn\sum_{n \ge 0} C {n+k-1 \choose k-1} \lambda ^n x^n∑n≥0​C(k−1n+k−1​)λnxn