badopy 1.2

61. Kiedy w grafie istnieje cykliczna droga Eulera?

Gdy dla każdego wierzchołka il. łuków wchodzących i il. łuków wychodzących są sobie równe

63. Kiedy graf skierowany jest cykliczny w sensie dróg?

Kiedy zawiera drogi cykliczne?

64. Kiedy graf skierowany jest acykliczny w sensie dróg?

Kiedy nie zawiera dróg cyklicznych?

65. Jakie warunki spełniają wierzchołki warstwy grafu?

- Dla warstwy zerowej należą wierzchołki niemające poprzedników - każdy wierzchołek ma poprzedniki tylko w warstwach wcześniejszych - każdy wierzchołek musi mieć poprzednik w warstwie poprzedzającej

66. Dla jakich grafów można wyznaczyć jego warstwy?

Dla grafów skierowanych acyklicznych w sensie dróg.

67. Jaki podgraf tworzą wierzchołki warstwy grafu?

Podgraf pusty

68. Do czego służy algorytm Leifmana?

Do wyznaczania wszystkich składowych silnej spójności.

69. Co to jest karkas grafu?

Jest to dowolny graf częściowy, spełniający dowolne dwa z podanych trzech warunków: m(T)= m(G) – λ(G) H(T) = H(G) λ(G) = 0

70. Co to jest najtańszy karkas grafu?

Jest to karkas, dla którego suma kosztów osiąga wartość minimalną.