Badopy 31-40

31. Co to jest podgraf?

Wybrana część wierzchołków grafu i wszystkie gałęzie incydentne z nimi.

32. Co to jest graf częściowy?

Wszystkie wierzchołki grafu i wybrana część gałęzi incydentnych z nimi.

33. Co to jest podgraf pusty?

Każdy taki podgraf, który jest grafem pustym.

34. Co to jest maksymalny podgraf pusty?

Taki podgraf pusty, że zbiór jego wierzchołków nie jest podzbiorem właściwym żadnego innego zbioru wierzchołków tworzącego podgraf pusty.

35. Wymień etapy metody wyznaczania optymalnego kolorowania wierzchołków grafu.

tworzymy maksymalne podgrafy puste; pokrycie minimalne, dobór kolorów, zaznaczamy od końca

36. Zdefiniuj problem pokryć minimalnych zbioru.

Mając pewien skończony zbiór W i ustalony zbiór podzbiorów Wk tego zbioru (k= 1,2, ..., K), spełniające warunek Uk=1 Wk = W, należy wybrać najmniejszą liczbę tych podzbiorów w ten sposób, aby w sumie tworzyły one cały zbiór W.

37. Wymień metody suboptymalnego kolorowania wierzchołków grafu.

metoda redukcji grafu; metoda macierzy podobieństw

38. Zdefiniuj problem kolorowania wierzchołków grafu.

Tak pokolorować, aby zużyć jak najmniejszą liczbę kolorów, pokolorować wszystkie, tak, aby sąsiednie wierzchołki były pokolorowane innym kolorem.

39. Podaj przykład zastosowania metody kolorowania wierzchołków grafu.

Kolorowanie mapy w taki sposób, aby sąsiednie państwa nie były pokolorowane na ten sam kolor.

40. Co to jest marszruta w grafie?

Jest to dowolny ciąg przemienny wierzchołków i gałęzi.