nextupprevious
Next:6.2 Грамматики, языки и автоматы
Up:6 Формулировки заданий
Previous:6 Формулировки заданий

6.1 Графы и системы дорог


1. $\downarrow$ Найти все вершины заданного графа, недостижимые от заданной его вершины.

2. $\downarrow$ Определить, верно ли, что для любой пары вершин заданного орграфа одна из этих вершин достижима от другой.

3. $\downarrow$ Определить, является ли ободом заданный граф.

4. $\downarrow$ Определить, является ли связным заданный граф.

5. $\downarrow$ Найти длину кратчайшего цикла в графе.

6. $\downarrow$ Для двух выделенных вершин графа построить соединяющий их простой путь.

7. Найти самый длинный простой путь в графе.

8. $\downarrow$ Найти все вершины графа, к которым существует путь заданной длины от выделенной его вершины.

9.$\downarrow$ Найти такую нумерацию вершин орграфа, при которой всякая дуга ведет от вершины с меньшим номером к вершине с большим номером.

10. $\downarrow$ Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине.

11. Источником орграфа называют вершину, от которой достижимы все другие вершины; стоком -- вершину, достижимую от всех других вершин. Найти все источники и стоки данного орграфа.

12. Известно, что заданный граф -- не дерево. Проверить, можно ли удалить из него одну вершину (вместе с инцидентными ей ребрами), чтобы в результате получилось дерево.

13. Подсчитать количество компонент связности в дополнении заданного графа.

14. Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вершинами и отлична от каждой из них.

15. $\downarrow$ Вершины и ребра графа называют его элементами. По графу $G$ построить граф $T(G)$, у которого в качестве вершин взяты элементы $G$, а две вершины смежны тогда и только тогда, когда соответствующие элементы в $G$ смежны или инцидентны.

16. $\downarrow$ Пусть $d(u)$ -- степень вершины $u$ в графе $G$. Степенью ребра $x=<u,v>$ назовем неупорядоченную пару $<d(u), d(v)>$. Определить, совпадают ли степени всех ребер заданного графа, и если нет, то можно ли удалить из него одну вершину (вместе с инцидентными ребрами) так, чтобы полученный граф обладал этим свойством.

17. $\downarrow$ По графу $G$ построить граф $K(G)$ с тем же множеством вершин, что и у $G$; вершины в $K(G)$ смежны тогда и только тогда, когда расстояние между ними в $G$ не превышает 2.

Проверить, совпадают ли степени всех вершин в $K(G)$, и если нет, то нельзя ли удалить из него одну вершину так, чтобы полученный граф удовлетворял этому требованию.

18. Задан орграф с циклами. Проверить, можно ли удалить одну вершину так, чтобы в полученном орграфе не было циклов длины меньше заданной.

19. $\downarrow$ По графу $G$ построить граф $G'$ следующим образом: в качестве вершин в $G'$ берутся ребра графа $G$: две вершины в $G'$ смежны тогда и только тогда, когда смежны соответствующие ребра в $G$. В $G'$ найти все вершины, расстояние от которых до некоторой выделенной равно 2.

20. В заданном дереве, все вершины которого имеют степень не больше 3, найти самый длинный путь от выделенной вершины до вершины со степенью 1.

21. $\downarrow$ Из графа удалить все вершины, от которых недостижима заданная вершина.

22. $\uparrow$ Для заданного натурального $n$$(n \geq 3)$ построить граф, не содержащий циклов длиной 3, в котором степени всех вершин равны 3.

23. Найти диаметр графа, т.е. максимум расстояний между всевозможными парами его вершин.

24. Вершина графа называется точкой сочленения, если ее удаление приводит к увеличению числа компонент связности. Найти все точки сочленения заданного графа.

25. Найти медиану графа, т.е. такую его вершину, что сумма расстояний от нее до остальных вершин минимальна.

26. По графу $G$ построить последовательность графов $G_1,\ldots,C_n$ с тем же множеством вершин, что и у $G$ (здесь $n$ -- максимум расстояний для пар вершин в $G$, между которыми имеется соединяющий их путь). Ребро между вершинами в $G_i$ проводится тогда и только тогда, когда расстояние между соответствующими вершинами в $G$ не превышает $i$.

27. Гамаком называется подграф заданного орграфа с таким непустым множеством вершин $A$, что существует не более одной вершины в $A$, к которой ведут дуги от вершин вне $A$, и не более одной вершины вне $A$, к которой ведут дуги от вершин множества $A$. Найти количество различных гамаков графа.

28. Задана система односторонних дорог. Найти путь, соединяющий города $A$ и $B$ и не проходящий через заданное множество дорог.

29. $\uparrow$ Система двусторонних дорог называется трисвязной, если для любой четверки разных городов $A,B,C,D$ существует два различных пути из $A$ в $D$, причем один из них проходит через $B$, а другой -- через $C$. Определить, является ли трисвязной заданная система двусторонних дорог.

30. В системе двусторонних дорог для каждой пары городов указать длину кратчайшего пути между ними.

31. $\uparrow$ Задана система двусторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую из дорог системы ровно один раз.

32. $\uparrow$ Задана система двусторонних дорог. Найти замкнутый путь длиной не более 100 км, проходящий через каждую дорогу ровно один раз.

33. $\downarrow$ В заданном графе указать все его четырехвершинные полные подграфы.

34. $\uparrow$ Задана система двусторонних дорог, причем для любой пары городов можно указать соединяющий их путь. Найти такой город, для которого сумма расстояний до остальных городов минимальна.

35. По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более 100 км.

36. $\uparrow$ По системе двусторонних дорог определить, можно ли, построив какие-нибудь новые три дороги длиной 10 км каждая, добраться из заданного города до каждого из остальных городов, проезжая не более 100 км.

37. По системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги, добиться того, чтобы из города $A$ нельзя было попасть в город $B$.

38. $\uparrow$ Задана система двусторонних дорог. $N$- периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше $N$. Определить $N$-периферию для заданного $N$.

39. Определить, можно ли в заданной системе односторонних дорог проехать из города $A$ в город $B$ таким образом, чтобы посетить город $C$ и не проезжать никакой дороги более одного раза.

40. В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города $A$ в город $B$ с минимальной величиной$S\times P$, где $S$ -- сумма длин дорог пути, а $P$ -- сумма пошлин проезжаемых дорог.

41. Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города $A$ в город $B$ (который может проходить как по железным, так и по шоссейным дорогам) и места пересадок с одного вида транспорта на другой на этом пути.

42. В орграфе без циклов выделены вершины $v$ и $w$. Найти какое-нибудь множество путей $M$ из $v$ в $w$ такое, что ни одна вершина, кроме $v$ и $w$, не лежит на двух путях из $M$ и любое расширение $M$ приводит к нарушению этого свойства.

43. $\downarrow$ Построить дерево двоичного поиска для заданного множества целых чисел и занумеровать его вершины в соответствии с их обходом во внутреннем порядке.

44. $\downarrow$ Построить дерево двоичного поиска для заданного множества целых чисел и занумеровать его вершины в соответствии с порядком прямого обхода этого дерева.

45. $\downarrow$ Построить дерево двоичного поиска для заданного множества целых чисел и занумеровать его вершины в соответствии с их порядком при обратном обходе этого дерева.

46. $\downarrow$ Множество целых чисел представить в виде дерева двоичного поиска и на основе этого представления напечатать числа в порядке убывания их значений.

47. Заданы граф и дерево. Удалить из графа часть ребер, чтобы полученный граф был изоморфен дереву.

48. $\uparrow$ К множеству целых чисел $S$, представленному в виде АВЛ-дерева, добавить число $n$ так, чтобы множество $S\cup \{ n \}$ также оказалось представленным в виде АВЛ-дерева.

49. $\uparrow$ Решить предыдущее задание для случая, когда число $n$ требуется удалить из множества $S$.

50. $\uparrow$ Множество целых чисел $S$ представляется в виде 2-3-дерева следующим образом: листьям приписываются элементы $S$ (в любом порядке), а нелисту $v$ -- наименьшее из чисел в поддереве с корнем $v$. По множествам $S_1$ и $S_2, S_1 \capS_2=\oslash$, построить соответствующее представление для $S_1 \cup S_2$.

51. $\uparrow$ Множество целых чисел $S$ представлено в виде 2-3-дерева следующим образом: листьям приписаны элементы $S$ в порядке возрастания слева направо; нелисту $v$ приписана пара чисел $(a,b)$, где $a$ -- наибольшее число в поддереве, корнем которого является самый левый преемник $v$, а$b$ -- наибольшее из чисел в поддереве, корень которого есть второй преемник $v$. Добавить к $S$ число $n$ так, чтобы множество $S\cup \{ n \}$ оказалось представленным таким же образом.

52. $\uparrow$ Решить предыдущее задание для случая, когда число $n$ требуется удалить из $S$.

53. Найти максимальное по числу вершин подмножество попарно несмежных вершин заданного графа.

54. Заданы граф и положительное число $k.$ Раскрасить вершины графы в $k$ красок, т.е. сопоставить каждой вершине графа число из отрезка $1,2,\ldots, k$ (краску) таким образом, чтобы смежным вершинам были сопоставлены разные числа.

55. Компонентой сильной связности в орграфе называется такой его подграф, в котором любые две вершины взаимно достижимы и который не содержится в другом подграфе, удовлетворяющем этому условию. Построить компоненты сильной связности для заданного орграфа.

56. Найти минимальное подмножество вершин заданного орграфа, от которых достижимы все остальные его вершины.

57. Определить, изоморфны ли два заданных графа.

58. Определить, изоморфен ли заданный граф своему дополнению.

59. Подсчитать количество попарно не изоморфных графов с $n$ вершинами и четырьмя ребрами.

60. Пусть фиксирована нумерация вершин орграфа. Дуга называется обратной при этой нумерации, если она ведет от вершины с большим номером к вершине с меньшим номером. Построить такую нумерацию вершин заданного орграфа, при которой число обратных дуг минимально.

61. Подмножество вершин графа называется доминирующим, если каждая вершина вне подмножества смежна хотя бы с одной вершиной этого подмножества. Найти минимальное по числу вершин доминирующее подмножество вершин заданного графа.

62. Говорят, что вершина графа накрывает ребро, если она инцидента этому ребру. Вершинным покрытием графа называется множество вершин, накрывающих все его ребра. Построить минимальное по числу вершин вершинное покрытие заданного графа.

63. Найти все подграфы заданного графа, которые являются ободами.

64. Граф называется вершинно-симметричным, если для любой пары его вершин существует автоморфизм, переводящий первую вершину во вторую. Определить, является ли вершинно-симметрическим заданный граф.

65. Вершину графа $a$ называют неподвижной, если она является неподвижной точкой любого его автоморфизма $\phi$, т.е. $\phi (a) = a$. Найти все неподвижные вершины заданного графа.

66. Определить, является ли заданный граф гамильтоновым.

67. Граф называется асимметричным, если у него имеется единственный автоморфизм -- тождественный. Определить, является ли асимметричным заданный граф.

68. $\downarrow$ Определить, является ли заданный граф двудольным, т.е. можно ли разбить множество его вершин на два подмножества так, чтобы каждое ребро соединяло вершины из разных подмножеств.

69. В графе найти максимальное (по количеству ребер) подмножество попарно несмежных ребер.

70. Ребро графа накрывает его вершину, если оно инцидентно этой вершине. Найти минимальное (по количеству ребер) подмножество ребер, накрывающих все вершины заданного графа.

71. Найти минимальное (по количеству ребер) подмножество ребер, удаление которых превращает заданный связный граф в несвязный.

72. В заданном графе найти максимальный по количеству вершин полный подграф.

73. $\downarrow$$v$-интервалом орграфа называется максимальный среди его подграфов $G$, который можно построить по следующим правилам: (1) вершина $v$ включается в пустой граф $G$; (2) если все предшественники некоторой вершины $u$ уже содержатся в $G$, то $u$ также включается в $G$. Построить $v$-интервалы для всех вершин $v$ заданного орграфа.

74. $\uparrow$ Пусть $G$ -- орграф, в вершинах которого расположены фишки, а состояние $G$ задается количеством фишек в каждой из его вершин. Говорят, что состояние $s'$ достижимо из состояния $s$ за один шаг, если $s'$ можно получить из $s$ следующим образом: сначала удаляются все фишки, находящиеся в одной из его вершин (скажем, в вершине $p$), а затем такое же количество фишек добавляется каждому преемнику вершины $p$. Найти все (различные) состояния $G$, которые достижимы из некоторого заданного не более, чем за $k$ шагов.

75. $\uparrow$ Решить предыдущее задание, изменив понятие достижимости следующим образом: $s'$ достижимо из $s$ за один шаг, если существует вершина $p$, каждый предшественник которой имеет хотя бы одну фишку, а $s'$ получается из $s$ удалением одной фишки у каждого предшественника вершины $p$ и добавлением одной фишки каждому преемнику вершины $p$.

76. Мостом графа называется такое ребро, удаление которого увеличивает число компонент связности графа. Найти все мосты заданного графа.

77. Подсчитать количество попарно не изоморфных графов, содержащих не более четырех вершин.

78. Треугольником графа называют всякую тройку различных и попарно смежных вершин этого графа. Склеиванием треугольника называется следующая операция: три вершины, составляющие треугольник, удаляются из графа вместе со всеми инцидентными им ребрами; добавляется новая вершина $v$, а ребро $<w,v>$ добавляется тогда и только тогда, когда вершина $w$ была смежна хотя бы с одной вершиной удаленного треугольника. Последовательным применением операции склеивания треугольника преобразовать исходный граф в такой, в котором нет треугольников.

79. По орграфу $G$ построить орграф $G'$, который получается из $G$ последовательным применением (пока это возможно) следующих преобразований: (1) если $v$ -- вершина из $G$ с единственным предшественником $u$$(u \neq v)$ и единственным преемником $w$$(w \neq v)$, то она удаляется из $G$ вместе с дугами $(u,v)$ и $(v,w)$, а затем добавляется новая дуга $(u,w)$; (2) если $v$ -- вершина без предшественников и преемников, то она просто удаляется из $G$.

80. Через $\Gamma_G(W)$ обозначим подмножество вершин орграфа $G=(V,E)$, которые являются преемниками вершин из $W$. Найти такое максимальное по числу вершин подмножество $W$$(W \subsetV, W \neq V)$ вершин заданного графа, для которого $\Gamma_G(W) \subset W$.

81. $\uparrow$ Найти длину самого длинного простого пути от города $A$ до города$B$ в заданной системе односторонних дорог.

82. По заданной системе односторонних дорог определить, есть ли в ней город, куда можно попасть из любого другого города, проезжая не более 100 км.

83. По заданному орграфу $G$ построить орграф его транзитивного замыкания, т.е. такой орграф $G'$, в котором множество вершин совпадает с множеством вершин $G$, а любые две его вершины $u,v$ являются смежными тогда и только тогда, когда в $G$ существует путь из $u$ к $v$.

84. $\downarrow$ Проверить, является ли заданный граф транзитивным, т.е. таким, что для любых трех вершин $u,v,w$ выполняется условие: если вершины $u$ и $w$, а также $v$ и $w$ смежны, то вершины $u$ и $v$ также смежны.

85. Для заданного целого $n>0$ построить граф с $n$ вершинами, в котором степень каждой вершины равна 4.

86. Найти количество разных простых путей, соединяющих пары вершин заданного ориентированного графа.

87. Задан ориентированный ациклический граф. Найти минимальное число попарно непересекающихся простых путей, содержащих все вершины графа.

88. $\downarrow$ По заданной вершине графа распечатать все вершины, из которых есть путь в данную. Вершины должны печататься в порядке не убывания их расстояния до заданной: сначала сама вершина, потом ее соседи, потом соседи соседей (еще не напечатанные) и т.д.

89. Заданы система односторонних дорог и положительное число $X$. Подсчитать количество разных простых путей длины $Y$, $X\leqY$, между двумя заданными городами.

90. Заданы граф и целое положительное число $K$. Подмножество вершин графа называется независимым, если никакие две вершины не соединены в графе ребром. Найти разбиение множества вершин $V$ исходного графа на такие независимые подмножества $V_1,V_2,\ldots,V_k$, где $k \geq K$, что объединение любой пары $V_i$ и $V_j$, $1 \leq i < j \leq k$, не есть независимое множество.

91. Заданы два графа $G$ и $H$, такие, что $G$ содержит в заданное число $k$ раз больше вершин, чем $H$. Раскрасить вершины $G$ в $k$ цветов так, чтобы любой подграф $G$, образованный всеми одноцветными вершинами, был изоморфен графу $H$.

2. Заданы система односторонних дорог и положительные числа $K$ и $S$. Найти такое подмножество из $k$ дорог, где $k \leq K$, которое содержит по крайней мере одну дорогу из каждого замкнутого маршрута, имеющего длину не более $S$.

93. Проверить, можно ли раскрасить ребра графа в два цвета так, чтобы в графе не было треугольника, ребра которого окрашены одним цветом.

94. Заданы граф $G$ и положительное целое число $K$. Раскрасить вершины $G$ в $k$ цветов, где $k \leq K$, таким образом, чтобы был ациклическим любой подграф, образованный всеми одноцветными вершинами.

95. Решить задание 94 таким образом, чтобы был полным любой подграф, образованный всеми одноцветными вершинами.

96. Решить задание 94 таким образом, чтобы любой подграф, образованный всеми одноцветными вершинами, состоял только из вершин степени 1.

97. Заданы граф, положительное целое число $K$ и неотрицательное целое число $S$. Можно ли удалить часть ребер из графа таким образом, чтобы осталось не менее $K$ ребер, граф был бы связным и не имел вершин степени более $S$.

98. Задан орграф $G$ и положительное целое число $K$. Можно ли удалить из орграфа часть дуг таким образом, чтобы осталось не менее $K$ дуг и для любой пары его вершин имелся по крайней мере один путь, соединяющий их.

99. Задан граф. Удалить из него часть ребер (но не все!) таким образом, чтобы любая вершина имела степень равную 3 или 0.

100. Задан орграф, в котором выделены две вершины, и целое число $K$. Пометить не более $K$ дуг так, чтобы для любых двух путей, соединяющих две выделенные вершины, существовала помеченная дуга, принадлежащая ровно одному пути.
 

Next:6.2 Грамматики, языки и автоматы
Up:6 Формулировки заданий
Previous:6 Формулировки заданий


© В.Н. Касьянов, Е.В.Касьянова, 2004