Методические указания к курсу «Элементы дискретной математики и биоинформатики» (стр. 3 из 8)

		1	1	1	0	0	0	0	0	0	0
		1	0	0	1	1	0	0	0	0	0
		0	0	0	1	0	1	1	0	0	0
		0	1	0	0	1	1	0	1	0	0
		0	0	1	0	0	0	0	0	1	0
		0	0	0	0	0	0	0	1	1	1
		0	0	0	0	0	0	1	0	0	1

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

Расстоянием

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

. Здесь – это множество вершин графа .

Радиус графа G определяется как наименьший из условных радиусов графа, а центр графа составляют вершины, условные радиусы графа относительно которых совпадают с радиусом графа.

Для данного графа таблица расстояний и условных радиусов вершин имеет вид:

	0	1	2	1	1	2	3	3
	1	0	1	1	2	2	2	2
	2	1	0	1	3	2	1	3
	1	1	1	0	2	1	2	2
	1	2	3	2	0	1	2	3
	2	2	2	1	1	0	1	2
	3	2	1	2	2	1	0	3

Радиус графа

, следовательно, центр графа – это множество вершин .

5.3. Из одной бактерии в результате деления получилось 1000 бактерий: вначале бактерия разделилась на две, затем одна из них вновь разделилась на две, затем одна из трех бактерий разделилась на две и т.д. Докажите, что в некоторый момент существовала бактерия, число потомков которой в самом конце, т.е. среди 1000 бактерий не меньше 100 и не больше 199.

Решение. Процесс деления бактерий опишем корневым деревом. Условимся называть дочками бактерии те две бактерии, на которые она разделилась. Обозначим через Б₁, Б₂, Б₃, … такую последовательность бактерий:

Б₁ – исходная бактерия, число ее потомков П₁=1000;

Б₂ – та из дочек Б₁, у которой число потомков не меньше, чем у другой дочки бактерии Б₁;

Б₃ – та из дочек Б₂, у которой число потомков не меньше, чем у другой дочки бактерии Б₂ и т.д.