Деревья

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

90. Докажите, что в дереве любые две вершины соединены ровно одной цепью.

91. Докажите, что в дереве с р вершинами р–1 ребро.

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

93. Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).

94. Докажите, что в любом нетривиальном дереве имеются, по крайней мере, две висячие вершины.

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

96. Какое максимальное число висячих вершин может иметь дерево, обладающее 9 вершинами?

97. В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.

98. В парке «Лотос» невозможно найти такой маршрут для прогулок по его дорожкам, который начинается и оканчивается в одной и той же точке и каждую дорожку содержит не более одного раза. Докажите, что некоторые дорожки парка приводят в тупик.

99. В стране 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?

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

101. Сколько ребер нужно удалить из связного графа, имеющего q ребер и p вершин, чтобы получить дерево, содержащее все вершины этого графа.

102. Докажите, что полный двудольный граф с n вершинами в одной доле и m вершинами в другой имеет не менее mn-m-n+1 различных циклов?

103. Найдите цикломатическое число для графов:

∙ К_n;

∙ К_m,n;

∙ W_n;

∙ графа Петерсона;

∙ любого связного регулярного графа с n вершинами степени регулярности r.

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

105. В несвязном графе с 5 компонентами связности любое ребро является мостом. Сколько вершин в графе, если ребер 115? (1 балл)

106.

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

107. Найдите какие-нибудь остовные деревья для графов К₅, К₃₃, и в графе Петерсона.

108. Найти минимальный каркас графа, изображенного на рисунке, используя алгоритм Краскала.

109. Постройте каркас минимального веса для графа заданного матрицей весов (2 балла)

		¥	¥	¥		¥
		¥	¥		¥
¥	¥				¥
¥	¥				¥
¥						¥
	¥	¥	¥			¥
¥				¥	¥

		¥	¥	¥
			¥	¥
¥				¥	¥	¥
¥	¥					¥
¥	¥	¥				¥
		¥
	¥	¥	¥	¥

	¥	¥	¥	¥
¥			¥	¥		¥
¥			¥	¥		¥
¥	¥	¥				¥
¥	¥	¥				¥
	¥	¥	¥	¥

110. Найти каркас минимального веса для полного графа на множестве вершин (х1, х2, х3, х4), как показано на рисунке, с весами ребер, определенных как расстояния между вершинами.

111.

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

112. Необходимо построить систему нефтепроводов, которые должны соединять семь нефтеочистительных заводов (Н1, Н2, Н3, Н4, Н5, Н6, Н7), принадлежащих некоторой компании, с портом (П), куда поступает импортируемая сырая нефть. Стоимость прокладки нефтепровода между любыми двумя пунктами составляет 5000 долларов в расчете на одну милю. расстояния между всеми парами вершин задаются в следующей таблице:

	П	Н1	Н2	Н3	Н4	Н5	Н6	Н7
П
Н1
Н2
Н3
Н4
Н5
Н6
Н7

Найдите минимальную стоимость прокладки нефтепровода.

113. Борцовский турнир с 13 участниками проводится по олимпийской системе, при которой проигравший выбывает. На одну встречу, с учетом подготовки к ней и отдыха участника, отводится один час. Сколько времени нужно, чтобы провести турнир, если в распоряжении организаторов только 5 борцовских ковров?

114. Есть бактерия, которая делится на 3 бактерии. В дальнейшем появляющиеся бактерии могут делиться на 4 бактерии, могут делиться на две, а могут и не делиться. Образовалось 102 бактерии. Определите число делений, если известно, что число бактерий, разделившихся на две в 6 раз больше, чем число бактерий, разделившихся на четыре.

115. Насыщенным углеводородом называется соединение углерода С, имеющего валентность 4, и водорода Р, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Напишите формулу насыщенного углеводорода, содержащего n атомов углерода.

116. Город имеет форму квадрата (100n x 100n) метров с (n+1) прямолинейной улицей, идущей параллельно одной стороне квадрата, и (n+1) прямолинейной улицей, идущей параллельно другой его стороне. Расстояние между любыми двумя соседними параллельными улицами – 100 метров, длина каждой улицы – 100n метров. Мэр города решил выполнить свое предвыборное обещание: заасфальтировать за свой счет улицы так, чтобы с любого перекрестка на любой другой можно было проехать по асфальту. Конечно, мэр хочет истратить как можно меньше своих денег. Какой наименьшей длины асфальтовое покрытие улиц может сделать мэр?

117. Несколько авиакомпаний решили связать авиалиниями 100 городов так, чтобы выполнялось два условия:

∙ любые два города были соединены беспосадочной линией не более чем одной компании;

∙ любая авиакомпания, пользуясь своими линиями, могла бы доставить пассажира из любого города в любой другой (возможно с пересадками).

При каком наибольшем числе авиакомпаний такое решение осуществимо?

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

∙ никто из членов шайки, кроме главаря, не умеет считать;

∙ все члены шайки, кроме главаря, умеют считать.

Дата добавления: 2015-01-03