Задача 1 термин "социомéтрия"

Вид материала

Задача

Содержание V и множество E Решение задачи 1. Теорема (без доказательства) Решение задачи 2. Решение задачи 3.

Подобный материал:

• Asis of the analysis of operating statutory acts problems of the terminology used, 1462.51kb.
• Карму Термин «карма», 138.35kb.
• Евгений Поникаров, 3340.72kb.
• Введение Термин «экономика», 696.15kb.
• Наукоемкие предприятия, 65.99kb.
• Программа курса лекций «Математические методы и модели исследования операций», 27.98kb.
• Т. М. Боровська кандидат технічних наук, доцент І. С. Колесник, 118.17kb.
• Доклад 6 октября 2005 года. Введение. Термин «нанотехнология», 18.23kb.
• Гражданское право, 60.32kb.
• Лизинг Термин "лизинг", 251.41kb.

Решение задач в социальных и естественных науках

с помощью графов


Задача 1 (термин "социомéтрия" появился в 19 в. в связи с попытками применить математические методы к изучению социальных явлений).

Десять кандидатов готовятся к двум космическим экспедициям. Поскольку экспедиции будут продолжаться несколько лет, а их участники окажутся в замкнутом пространстве небольшого объема, то большое значение приобретает психологическая совместимость членов экипажа. Путем тестирования были установлены пары кандидатов, присутствие которых в одной и той же экспедиции было бы нежелательно. Результаты тестирования отражены в таблице (знак "+" означает, что соответствующая пара кандидатов является несовместимой). Разделите кандидатов на две группы для участия в экспедициях.

	1	2	3	4	5	6	7	8	9	10
1		+	+	+
2	+				+
3	+						+
4	+					+
5		+						+
6				+						+
7			+					+		+
8					+		+		+
9								+		+
10						+	+		+

Задача 2.

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


Задача 3.

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

Для решения задач нам понадобятся некоторые сведения из теории графов.

Пусть задано некоторое непустое множество  V и множество E пар различных элементов из V. Пара (V,E) называется графом, элементы множества V называются вершинами графа, элементы множества E – ребрами. Если две вершины графа соединены ребром, то такие вершины называются смежными. Вершины, соединенные ребром, называются его концами. Будем обозначать вершины графа v₀, v₁, v₂, ... , v_k, а ребра – e₀, e₁, e₂, ... , e_k, или указанием его концов – (v_i, v_k).

Число ребер, выходящих из вершины v, называется степенью вершины и обозначается d(v). Вершина степени ноль называется изолированной, вершина степени 1 – висячей. Очевидно, если n – число вершин графа, то для любой вершины v: 0  d(v)  n – 1.


Лемма 1 (о рукопожатиях).

Сумма степеней вершин графа равна удвоенному числу ребер.

Доказательство.

Пусть граф G имеет n вершин. Сложив степени вершин графа G d(v₁), d(v₂), ..., d(v_n), мы получим сумму, в которую каждое ребро входит дважды (поскольку каждое ребро вносит по единице в степень ровно двух вершин). Поэтому d(v₁) + d(v₂) + ... + d(v_n) = 2E. Лемма доказана.


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


Решение задачи 1.

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



Рассмотрим следующую процедуру, которая называется поиском в ширину и позволяет проверить, является ли граф двудольным. Вершину 1 отнесем к первой группе (для этого на рисунке обведем номер соответствующей вершины кружочком). Затем смежные с ней вершины 2, 3, 4 отнесем ко второй группе (обведем номера квадратиком). Смежные с одной из вершин 2, 3, 4 вершины 5, 6, 7 отнесем к первой группе, и так далее, пока не разделим все вершины на две группы. В первую группу попали вершины 1, 5, 7, 6 и 9, во вторую – 2, 3, 4, 8, 10. Это разделение вершин соответствует делению кандидатов на группы для участия в экспедициях.


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

Цепью в графе называется такая чередующаяся последовательность вершин и ребер графа

(v₀, e₀, v₁, e₁, v₂, e₂, ... , e_k–1, v_k)

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

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


Теорема (без доказательства)

Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины четная.


Лемма 2.

В каждом дереве есть висячая вершина.

Доказательство.

Предположим противное. Рассмотрим произвольную вершину v₁ и перейдем из нее по любому ребру (v₁, v₂) в вершину v₂. Поскольку степень вершины v₂ не меньше двух, то из нее по новому ребру можно перейти в вершину v₃, и так далее. Поскольку число вершин в графе конечно, то в конце концов мы придем в одну из тех вершин, в которых были раньше. Это означает существование цикла в дереве, что противоречит условию. Следовательно, в дереве есть висячая вершина. Лемма доказана.


Лемма 3.

В любом дереве число ребер на единицу меньше числа вершин.

Доказательство.

Из леммы 2 имеем, что каждое дерево имеет висячую вершину. Удалим висячую вершину v₀ из дерева G вместе с ребром, выходящим из этой вершины. Полученный граф G₀ будет связным, и в нем будут отсутствовать циклы, то есть граф G₀ – тоже дерево. Из графа G₀, найдя и затем удалив висячую вершину v₁ вместе с выходящим из нее ребром, можно получить дерево G₁, и так далее. Выполнив такие операции, мы получим последовательность деревьев G, G₁, G₁, ..., которая заканчивается деревом, состоящим из одной вершины и не имеющим ребер. Для этого дерева выполняется соотношение m = n – 1, где m – количество ребер, а n – число вершин графа. Теперь будем добавлять в обратном порядке ранее удаленные вершины и ребра. При каждом возвращении добавляется одна вершина и одно ребро, следовательно, для каждого получающегося графа соотношение m = n – 1 будет выполняться. Лемма доказана.


Решение задачи 2.

Процесс деления бактерий можно изобразить деревом.



Начальной бактерии будет соответствовать вершина степени 2. Любая бактерия (кроме исходной), разделившаяся на две бактерии, будет соответствовать вершине степени 3, а бактерия, разделившаяся на 4 – вершине степени 5. Бактерии, которые не делились (их 102), соответствуют вершинам степени 1.



Пусть молекула насыщенного углеводорода содержит n атомов углерода и m атомов водорода. Граф молекулы является деревом, поэтому согласно лемме 3 он имеет n + m вершин и n + m – 1 ребер.