Графы и их применение

     Выясним причину этого затруднения. Отправимся из вершины А1, которую будем относить к классу О. Если А1 является одним из родителей В1, то другой родитель А2 относится к М. Если А2, кроме того, является родителем В2, то другой родитель А3 относится к классу О и т.д. Так получим "чередующуюся" последовательность А1,А2,...,Аn (3) индивидуумов, попеременно относящихся к классам О и М. На графе они связаны последовательностью ребер (А1,В1),(В1,А2),(А2,В2),(В2,А3),..., в которой каждые два соседних ребра находятся в противоположных направлениях. (рис. 15)

   Предположим теперь, что А₁ и А_n является родителями В_n, как на рис. 15. Это дает "чередующийся" цикл (А₁,В₁),(А₂,В₁),(А₂,В₂),...,(А_n,В_n),(А₁,В_n) (4)

   А₁ и А_n должны относится к разным классам, значит n должно быть четным.

   Условие родства. Пусть G - ориентированный граф, для которого условие (2) выполнено. если можно разделить вершины  графа G на два класса: класс "матерей" М и "отцов" О с соблюдением указанных выше условий, то каждая последовательность (3) родителей А_i в любом "чередующемся" цикле должна состоять из четного числа членов. эквивалентно условие состоит в том, что число ребер каждого "чередующегося" цикла (4) кратно четырем.

   Если  условие родства выполнено, то каждую вершину графа можно отнести к одному из указанных классов. Начнем с вершины А1 и отнесем ее к О или М. если А1 не имеет детей или если эти дети не имеют других известных нам родителей, то из определения класса А1 не вытекает никаких следствий. Если же А1 имеет детей, образуем всевозможные "чередующиеся" цепи, которые начинаются в А1. Этим будет определен класс для любого из родителей в последовательности (3).

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

   Может ли граф, удовлетворяющий этому условию, отображать результаты некоторого генетического  эксперимента. Для этого придется наложить на граф еще одно дополнительное ограничение. Предположим, что мы имеем последовательность индивидуумов D1,D2,...,Dn, (5) где каждый Di является потомком предыдущего. На графе это дает ориентированную цепь D1,D2,...,Dn, (5) где каждый Di является потомком предыдущего. На графе это дает ориентированную цепь (рис. 16). Рождение этих особей (5) должны и по времени происходить в том же порядке; следовательно, не может случиться, чтобы Dn оказался родителем D1 (рис. 16), т.е. наш граф не должен содержать никакого ориентированного цикла; такие графы называются ациклическими.

   Итак, три условия, необходимые для того, чтобы некоторый ориентированный граф мог описывать генетический эксперимент.

   1) Для всех А справедливо неравенство  ρ*(А)≤2, т.е. никакая вершина не  имеет более двух входящих  ребер.

   2) Число ребер каждого "чередующегося" цикла кратно четырем.

   3) Граф является ациклическим.

   Эти три условия можно рассматривать  как условия, которым подчиняется  общая генетическая схема. На обычном  языке это очевидные истины:

   1) Каждое существо имеет, самое  большее, двух родителей.

   2) Один из родителей является отцом, а второй - матерь.

   3) Никто не может быть своим  собственным потомком.

    Упражнения. 

1.  Начертите граф, показывающий, что два индивидуума являются: а) двоюродными братьями (или сестрами, или братом и сестрой); б) тетей (или дядей) и племянником (или племянницей).

Решение:  

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

Решение:  
 
 
 
 

     СПИСОК  ЛИТЕРАТУРЫ

1. В.Н.  Бурков, Д.А. Новиков «Элементы  теории графов»

2. Е.Л  Рабкин, Ю.Б. Фарфоровская «Дискретная  математика»

3. Г.А.  Гончарова, А.А. Молчалин «Элементы  дискретной математики»

4. А.И.  Белоусов, С.Б. Ткачев «Дискретная  математика»

5. В.А.  Носов «Комбинаторика и теория  графов»

6. Г.  Е. Шикина «Исследование операций»

7. О.  Оре «Графы и их применение»