Теория графов

73. В районе автобусное сообщение устроено так, что любой город соединен автолинией не более, чем с тремя другими городами, и из любого города можно попасть в соседний, проехав не более, чем через один город. Какое наибольшее число городов может быть в районе?

74. В шахматном турнире по круговой системе участвуют 7 студентов. Известно, что Иван сыграл 6 партий, Анатолий – 5 партий, Алексей и Дмитрий – по 3, Семен и Илья – по 2, Евгений – 1. С кем сыграл Алексей?

75. Построить неориентированный граф по матрице инцидентности . Найти матрицы смежности вершин и ребер.

76. Построить неориентированный граф по матрице смежности вершин . Пронумеровать ребра, построить матрицу смежности ребер и матрицу инцидентности.

77. Имеется орграф ,,. Построить для него матрицы смежности, инцидентности, структуру смежности.

78. Дана матрица . Построить орграф, имеющийР матрицей смежности вершин. Найти матрицу инцидентности.

79. Для графов инайти,,.

80. Для графов инайти,,.

81. Для графов ипредставить в матричной и геометрической форме графы,,.

82. Для графов ипредставить в матричной и геометрической форме графы,,.

83. Вершины графа , упорядочить графическим и матричным методами. Построить наглядное изображение изоморфного графа.

84. Вершины орграфа :,упорядочить графическим и матричным методами. Построить наглядное изображение изоморфного графа.

85. Упорядочить вершины орграфа . Построить наглядное изображение изоморфного графа.

86. Упорядочить вершины орграфа . Построить наглядное изображение изоморфного графа.

87. Используя метод Магу, определить максимальные внутренне устойчивые и минимальные внешне устойчивые множества орграфа . Найти ядро графа.

88. Используя метод Магу, определить максимальные внутренне устойчивые и минимальные внешне устойчивые множества орграфа . Найти ядро графа.

89. Используя метод Магу, найти максимальные внутренне устойчивые и минимальные внешне устойчивые множества для орграфа . Найти ядро графа.

90. Используя метод Магу, найти ядро графа. Рассмотреть случаи: 1) ; 2)

91. Для орграфа найти функцию Гранди.

92. Построить функцию Гранди для графа, заданного списком последователей: 2 – 1, 7; 3 – 1, 2, 4; 4 – 1; 5 – 1, 4; 6 – 1, 5; 7 – 1, 6.

93. Разбить на уровни орграф, заданный списком последователей {1 – 2, 5, 7; 2 – 3, 5, 6; 4 – 3; 5 – 6; 7 – 4, 5, 6}. Найти функцию Гранди и ядро графа.

94. Разбить орграфы без контуров, заданные матрицами смежности вершин, на уровни. Найти функцию Гранди и ядра графов. Рассмотреть случаи 1) ; 2).

95. Определить матрицы достижимости и сильной связности для орграфов с матрицами смежности вершин 1) , 2).

96. Для орграфов, заданных матрицами смежности вершин, найти компоненты сильной связности графа. Построить изображение орграфа и компонент его сильной связности. Рассмотреть случаи: 1) , 2).

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

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

99. Методом латинской композиции найти все простые цепи длины 3 в орграфе .

100. Даны графы ,. В графеметодом латинской композиции найти все простые цепи длины 3 и выделить те из них, которые начинаются в вершине 2.

101. Даны графы ,. Построить графы,,. Для графанайти матрицы смежности вершин, достижимости, сильной связности. Найти компоненты сильной связности Методом латинской композиции найти все маршруты длины 4 и выделить те из них, которые проходят через вершину 3.

102. Даны графы ,. Построить графы,,. Для графанайти матрицы смежности вершин, достижимости, сильной связности. Найти компоненты сильной связности Методом латинской композиции в графенайти все маршруты длины 4 и выделить те из них, которые проходят через вершину 1.

103. Для орграфа, заданного матрицей смежности вершин , методом фронта волны найти минимальный путь из вершины 1 в 6.

104. Найти минимальный путь из v₁ в v₇ в орграфе, заданном матрицей смежности вершин ,.

105. Используя алгоритм Тэрри, найти замкнутый маршрут в графе, заданном структурой смежности , проходящий ровно по 2 раза (по 1 разу в каждом направлении) через каждое ребро графа.

106. Найти минимальный путь из v₁ в v₇ в орграфе, заданном матрицей смежности вершин .

107. Проверить, существуют ли в мультиграфе, заданном матрицей смежности вершин , эйлеровы цепи и циклы. Если да, то найти их.

108. Найти эйлерову цепь в графе, заданном структурой смежности .