Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Число способов, которыми можно пометить граф.

Читайте также:
  1. Quot;Недельные правила " можно оптимизировать
  2. Uuml;1. Возможность совмещения реагирующих между собой ингредиентов.
  3. V Ввод бокового пути можно осуществить, начиная от предвходного светофора при следовании по правильному пути.
  4. Z-функция строки. Число вхождений подстроки в строку.
  5. А вот можно личный вопрос? – Конечно. А вы когда-нибудь сами верили в судьбу?
  6. А что можно сказать про вас?
  7. Автор сетует на то, что мы не занимаемся гигиеной собственных мыслей, а также советует ЖЕЛАЮЩИМ, как можно научиться думать
  8. Автор утверждает, что в мире царит такой семантический шум, что договориться просто невозможно, а потом объясняет, что сделать это очень легко
  9. Алгоритм кластеризацїї як системоутворюючого фактору регіональної конкурентоспроможності
  10. Б) Точки зрения, в соответствии с которыми определяются симптомокомплексы

Граф G порядка p состоит из конечного непустого множества V=V(G), содержащего p вершин, и множества X из q неупорядоченных пар различных вершин; при таком определении автоматически исключаются петли (ребра, соединяющие вершину с ней самой) и кратные (параллельные) ребра. Пара x={u,v}, принадлежащая множеству X, называется ребром графа G и говорят, что ребро соединяет вершины u b v. Вершины u и v называют при этом смежными; вершина u и ребро х, так же как вершина v и ребро x, называются инцидентными друг другу. Граф с р вершинами и q ребрами называется (p,q)-графом.

Значительно удобнее и нагляднее представлять графы диаграммами. Рассмотрим граф G, выбранный случайным образом, с множеством вершин V={v1, v2, v3, v4} и множество ребер

Х={ { v1, v2,}, { v2, v3,}, { v3, v4,}, { v4, v1,}, { v1, v3,}}

Его изображение диаграммой дано на рис. 1. На этой диаграмме буквами

v1 v2

 

 

v3 v4

рис. 1 Граф с четырьмя вершинами и пятью ребрами

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

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

1 4 1 4 1 3 2 4 2 3 3 2

 

3 2 2 3 2 4 1 3 1 4 1 4

рис. 2 Шесть различных распределений пометок в графе

 

Возникают два естественных вопроса. Первый: “Сколько существует помеченных графов порядка р?” Второй: “Сколько существует графов порядка р?” Первый мы обсудим сейчас, а на второй будет исследоваться позже.

Мы ответим на первый вопрос, незначительно обобщив задачу следующим образом: Найти число помеченных графов с данным числом вершин и ребер. Пусть Gp(t) – многочлен, у которого коэффициент при tk равен числу помеченных графов порядка p, имеющих ровно k ребер (Gp(t) - производящая функция для помеченных графов с заданным числом вершин и ребер). Если V – множество из р вершин, то существует различных неупорядоченных пар этих вершин. В каждом помеченном графе с множеством вершин V любая пара вершин является либо смежной, либо нет. Следовательно, число помеченных графов с k ребрами равно .

Теорема. Производящая функция Gp(t) для помеченных графов порядка р задается соотношением

Gp(t)= = (1+ t)m, где m= (1)

Так как Gp(t)=(1+ t)m и число Gp помеченных графов порядка р равно Gp(1), то

Gp= . (2)

 

Для р=3 существует восемь помеченных графов порядка 3 и только четыре (непомеченных) графа этого порядка. Существует 64 помеченных графов порядка 4 и только 11 графов порядка 4. (Проверьте приведенные данные!).

Возникает вопрос: “Сколькими способами можно пометить данный граф?” Чтобы ответить на этот вопрос, мы должны рассмотреть симметрии, или автоморфизмы, графа:

Взаимно однозначное отображение α множества V(G) на множество V(G1), сохраняющее смежность, обычно называется изоморфизмом. G=G1, то α является автоморфизмом графа G. Совокупность всех автоморфизмов графа G, обозначаемая Г(G), образует группу, называемую группой графа G. Таким образом, элементы группы Г(G) являются подстановками (перестановками), действующими на множестве V. Например, граф G, изображенный на рис. 1, имеет в точности четыре автоморфизма, так что Г(G) содержит следующие перестановки, записанные здесь с использованием обычного представления в виде произведения циклов:

(v1)(v2)(v3)(v4), (v1)(v3)(v2v4), (v1 v3)(v2)(v4), (v1 v3)(v2v4).

Пусть s(G)=│ Г(G)│ - порядок группы Г(G), обозначающий число симметрий графа G. Тогда ответ на задачу распределения пометок, поставленную выше, содержится в следующей теореме.

Теорема. Число способов распределения пометок в данном графе порядка р равно

i(G)=p!/ s(G). (3)

Доказательство этого утверждения будет приведено позже. Для иллюстрации теоремы мы просто заметим, что граф G на рис. 1 имеет p!/ s(G)=4!/ 4=6 распределений пометок и шесть различных помеченных графов на рис. 2.

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

 

Ориентированный граф, или орграф, D порядка p состоит из конечного непустого множества V=V(D), различных p объектов, называемых верши нами, вместе с заданным множеством X содержащим q упорядоченных пар различных вершин из множества V. Пара x=(u,v), принадлежащая множеству X, называется дугой орграфа D и, говорят, что u смежна к вершине v; вершина u и дуга х являются инцидентными друг другу, так же как вершина v и дуга x. Полустепенью исхода вершины u называется число дуг, для которых вершина u является первой вершиной; полустепенью захода вершины u называется число дуг, для которых вершина u является второй вершиной. Для орграфа также возможно представление в виде диаграммы, которой мы будем обращаться, как с самим орграфом.

В помеченном орграфе порядка р вершинам приписываются целые числа от 1 до р, и группа орграфа D, обозначаемая Г(D), состоит из всех подстановок множества вершин V(D) орграфа D, сохраняющая смежность. Так как число помеченных орграфов порядка р, имеющих в точности k ребер, равно ,то получаем следующие результаты:

Теорема. Производящая функция Dp(t) для помеченных орграфов порядка р задается соотношением

Dp(t)= = (1+ t)p(p-1), (4)

Очевидно, что Dp(t)=Gp2(t), так что Dp(1)=2p(p-1)=Gp2(1)

 

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

Упражнение. Докажите, что число помеченных турниров порядка р, равно .

 




Дата добавления: 2015-09-11; просмотров: 26 | Поможем написать вашу работу | Нарушение авторских прав

Конкретная математика | Производящие функции для сочетаний. | Производящие функции для перестановок. | Решение линейных рекуррентных уравнений. | Числа Стирлинга первого и второго рода. | Представление перестановок в циклической форме. | Цикловые классы (типы). | Перестановки без единичных циклов | Композиции чисел. | Эйлеровы графы |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав