Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Элементы теории графов

Историческая справка и основные понятия

Теория графов как раздел дискретной математики имеет многочисленные предметные интерпретации. Не случайно она «открывалась» независимо несколько раз, к этому приводили потребности практики. Началом теории графов принято считать решение Эйлером в 1736 г. задачи о кенигсбергских мостах. При этом он нашел критерий существования в графе специального маршрута (эйлеров цикл). В середине XIX в. инженер-электрик Кирхгоф, исследуя электрические цепи, разработал теорию специальных типов графов. А математик Кели в 1857 г., занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемых деревьями, и решил перечислительные задачи для трех типов деревьев. В это же время появилась знаменитая «проблема четырех красок», попытки решения которой привели к появлению новых понятий и серьезных результатов в теории графов. В XX в. психолог Левин фактически использовал графы для описания «жизненного пространства» индивидуума, эта идея нашла приложения в других психологических исследованиях. Физики-теоретики для «внутренних» нужд своей науки «открывали» теорию графов не один раз. Сам термин «граф» появился в 1936 г. в книге венгерского математика Кенига.

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

Определение ^.i. Граф G - это пара множеств, G=(V,E), где V - произвольное непустое множество, элементы которого принято называть вершинами, а Е - множество неупорядоченных пар различных вершин, которые называются ребрами.

Пусть V = {гц,...,vn} - конечное множество вершин, V=n- число вершин графа G, и E = {(vi,Vj)vi,VjCV и v%Фv3}, |jE|=m - число ребер графа G (заметим, что г,Vj) = (гу, щ), так как по определению рассматриваются неупорядоченные пары вершин), тогда G называется (п, т)-графом.

В силу определения 4.1 множество ребер Е графа G является подмножеством декартова квадрата множества V (Е С V х К), т. е. представляет собой бинарное отношение на множестве V. Причем это отношение антирефлексивное и симметричное, так как по определению (v. v) ^ Е и рассматриваются неупорядоченные пары вершин. Обратно, если рассматривать произвольное непустое множество V с заданным на нем нерефлексивным, симметричным бинарным отношением Е, то мы получим граф G={V,E).

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

графом G называется непустое множество V с заданным на нем антирефлексивпым, симметричным, бинарным, отношением ЕС V х V.

Если в определении графа рассматривать упорядоченные пары вершин пригну), то получим понятие ориентирован

ного графа или орграфа. В орграфе вершина иг называется началом, Vj - концом ребра е = (vi,Vj) ? Е. а сами ребра называются дугами. Орграфом, например, можно описать отношение подчиненности между структурными подразделениями некоторой организации.

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

Мультиграф, в котором допускаются ребра вида (v,v) (петли), на- з ы в а ет ся п сев до гра ф ом.

Определение ^.2. Бинарное отношение Е на множестве вершин графа G=(V,E) называется отношением смежности. Если (и. н) ? /у то вершины v,ueV называются смежным,и.

С каждым графом, кроме отношения смежности вершин, можно связать еще два бинарных отношения: отношение инцидентности на

V. х Е и отношение смежности на множестве ребер Е.

Определение 4-3. В графе G = (V, Е) вершина v ? V. и ребро е^Е называется инцидентными, если e = (v,w) (или e = (w,v)) для некоторой вершины w ? V.

Определение 4-4- Два ребра е и е2 в графе G=(V,E) называются смежными, если они инцидентны одной и той же вершине v ? V., т. е. если ei = (ц, гг), в2 = (г;, w).

Важной числовой характеристикой графа является понятие степени вершины.

Определение ^.5. Степенью вершины v графа G = (V, Е) называется число ?(ц), которое равно числу ребер, инцидентных этой вершине.

Определение 4-6- Вершина v графа G называется изолированной, если <5(г;) = 0, и концевой; (висячей), если ?(ц) = 1.

Докажем два простых, но важных факта о степенях вершин про- из во ль I ю го графа.

Теорема 4.1. Сумма степеней всех вершин графа G = (V,E) является четным числом, оно равно удвоенному числу ребер,

Доказательство. Доказываемое равенство следует из того, что каждое ребро e = (v,w) учитывается при подсчете степени вершины v и при подсчете степени вершины w, т. е. входит в сумму дважды.

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

Доказательство. Пусть V - множество вершин нечетной степени, a Vo множество вершин четной степени графа G=(V,E). Тогда V. = V U Vo и Vi П Vq = 0, следовательно,

Ясно, что ^2 d(vo) = 2k - четное число (к - целое), а так как Y) 5(v) = 2E, то ^2 S(v) = 2(E — к) тоже четное число.

veV ve

В ориентированном графе множество ребер, инцидентных вершине v, делится на два подмножества: ребра, для которых вершина v является началом, и ребра, для которых вершина v является концом.

Определение ^.7. Полу степенью исхода вершины v орграфа G— (V, Е) называется число d_(v), равное числу ребер, для которых она является началом. Полу степенью захода вершины v орграфа С = (У; Е) называется число ф_(г>), равное числу ребер, для которых эта вершина является концом.

В задачах теории графов иногда возникает необходимость изучать не весь граф целиком, а некоторую его часть.

Определение 4-8- Граф // = (У, Е) называется подграфом графа С =Е), если V] С У и Е С Е. Если У = У, то подграф II называется остовным подграфом.

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

Определение 4-9. Граф Н— (У,Е) называется подграфом, порожденным множеством вершин У (У ф 0) графа G= (У /Д, если любые две вершины v и w из У, смежные в графе являются смежными в графе //, т. е. если (v, w) ? Е) то (v, w) ? Е.

Таким образом, в подграфе, порожденном некоторым подмножеством вершин У, сохраняются все ребра исходного графа, инцидентные вершинам множества У.

Пример 4.1. Дан граф G = (У; /Г), V = {щ, гь, гц, щ, v$, Vq, Vj, v$, v9}, E={(vi,г;2), (гщщ), (Уь^б), (v2,v3), (v2,v5), (Уз,У>)> (УцУф

(грд/’в)}. Привести примеры остовного подграфа и подграфа, порожденного множеством вершин У = {v, г>з, щ, Нб, v%}•

Остовным подграфом графа G например, является граф 11= (Vi Е9, V, = {vUV2,V3,V4, VS, V6,V7, Щ, Щ, Ei = {(vUV2), (Vl,V6),

(v2,v3),(v2,v9),(v3,v5)}.

Подграф, порожденный множеством вершин У, в отличие от остовного, определяется однозначно. Это подграф G = (У, Е2), У = {гц, «з, г'5, г'б, vs }, E2={(vi,v6),(v3 ,v5),(v3 }.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>