Ориентированные графы и мультиграфы

112. Решите задачу 35. Граф может быть орграфом или мультиграфом.

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

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

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

116. Изобразите матрицы смежности и инциденций ориентированного графа:

117. Дана матрица смежности. Изобразить граф, ей соответствующий.

а)

б)

118. Из города А в город В ведут несколько дорог (карта дорог на рисунке). Найдите число маршрутов из А в В, учитывая, что при движении необходимо всегда приближаться к В.

119. Может ли в ориентированном графе полустепень захода каждой вершины быть равна 3, а полустепень исхода – 4?

120. В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

121. В некотором государстве 101 город. а) Каждый город соединен с каждым дорогой с односторонним движением, причем в каждый город входит 50 дорог и из каждого города выходит 50 дорог. Докажите, что из любого города можно доехать в любой другой, проехав не более чем по двум дорогам; б) Некоторые города соединены дорогами с односторонним движением, причем в каждый город входит 40 дорог и из каждого города выходит 40 дорог. Докажите, что из любого города можно добраться до любого другого, проехав не более чем по трем дорогам

122. В стране Ориентация на всех дорогах введено одностороннее движение, причем из любого города в любой другой можно добраться, проехав не более чем по двум дорогам. Одну дорогу закрыли на ремонт так, что из каждого города по-прежнему можно добраться до каждого. Докажите, что для любых двух городов это можно сделать, проехав не более, чем по трем дорогам.

123. Найдите компоненты сильной связности графа, заданного матрицей смежности:

124. Найдите компоненты сильной связности графа:

125. Решите задачу 62, считая, что заданы матрицы смежности ориентированного графа.

126. Дана матрица смежности графа, определить, является ли он эйлеровым. Ответ обоснуйте.

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

128. По заданной матрице весов графа G найти величину минимального пути и сам путь от вершины 1 до вершины 6 по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами:

	-				∞	∞
	∞	-				∞
	∞	∞	-
	∞	∞	∞	-
	∞	∞	∞	∞	-
	∞	∞	∞	∞	∞	-

	-					∞
	∞	-		∞	∞	∞
	∞	∞	-	∞	∞
	∞			-		∞
	∞			∞	-
	∞	∞	∞	∞	∞	-

	-					∞
	∞	-	∞
	∞		-
	∞	∞	∞	-
	∞	∞	∞	∞	-
	∞	∞	∞	∞	∞	-

129. В связном неориентированном графе степени всех вершин четны. Докажите, что на ребрах этого графа можно расставить стрелки так, чтобы выполнялись следующие условия: а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой; б) для каждой вершины числа входящих и выходящих ребер равны.

130. На плоскости отмечено некоторое конечное число точек. Некоторые пары точек являются началами и концами векторов, причем число векторов, выходящих из любой точки равно числу входящих в неё. Найдите сумму векторов.

131. В некоторой стране каждый город соединен с каждым дорогой с односторонним движением. Докажите, что найдется город, из которого можно добраться в любой другой.

132. Несколько команд сыграли между собой круговой турнир по волейболу. Будем говорить, что команда А сильнее команды В, если либо А выиграла у В, либо существует команда С такая, что А выиграла у С, а С - у В. а) Докажите, что есть команда, которая сильнее всех. б) Докажите, что команда, выигравшая турнир, сильнее всех.

133. В одном государстве 100 городов, и каждый соединен с каждым дорогой с односторонним движением. Докажите, что можно поменять направление движения на одной дороге так, чтобы от любого города можно было доехать до любого другого.

134. 20 команд сыграли круговой турнир по волейболу. Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я - у 3-й,..., 19-я у 20-й.

135. Докажите, что если победитель турнира по волейболу, проведенного по круговой системе, проиграл команде В, то существует команда С, выигравшая у В, у которой выиграл победитель.

136. Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В и С такие, что А выиграла у В, В выиграла у С, а С выиграла у А.

Дата добавления: 2014-12-29