Лекция № 15. Графы: основные понятия и операции.

РАЗДЕЛ IV. ТЕОРИЯ ГРАФОВ.

Пример 6.

а) В отделе работают 10 сотрудников. Требуется отобрать трёх из них для того, чтобы направить в командировку. Сколькими способами можно это сделать?

Поскольку имеет значение только то, какие именно сотрудники отобраны, то речь идёт о сочетаниях без повторений по 3 элемента из 10. Получаем:

б) В цветочном магазине имеются в продаже 5 различных видов цветов. Покупателю требуется составить букет из 7 цветов. Сколькими способами можно это сделать?

Будем считать различными те букеты, которые отличаются друг от друга по подбору цветов. Поскольку цветы в букете могут повторяться, то речь идёт о сочетаниях с повторениями по 7 элементов из 5. Тогда получим .

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

.

С частными случаями применения этой формулы ( для случаев и ) сталкиваются ещё в школе при изучении формул сокращённого умножения:

.

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

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

…………………..

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

1. Графы, их вершины, рёбра и дуги. Изображение графов.

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

При этом элементы множества V называются вершинами графа, а элементы множества E – ребрами.

Определение. Если вершина v является концом ребра , то говорят, что v и инцидентны.

В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями (на рисунке 1.4 при вершине 5 имеется петля). Одинаковые пары в множестве E называются кратными (или параллельными) ребрами. Количество одинаковых пар (v, w) в E называется кратностьюребра (v, w). Например, на рисунке 1.1 все рёбра имеют кратность 1, а на рисунке 1.2 есть два ребра, соединяющих одни и те же вершины 1 и 4, следовательно, их кратность равна двум.

Множество V и набор E определяют граф с кратными ребрами – псевдограф.

Псевдограф без петель называется мультиграфом.

Если в наборе E ни одна пара не встречается более одного раза, то мультиграф называется графом.

Ниже, на рисунке 1.1 изображен граф, на рисунке 1.2 мультиграф, на рисунке 1.4 – псевдограф.

Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины. На рисунке 1 изображены некоторые неориентированные графы.