Помощь по Теле2, тарифы, вопросы

Цель работы : Приобрести навыки решения задач частотного анализа с помощью функции рабочего листа анализа MS Excel .

Краткая теория

При анализе экономических показателей часто возникает вопрос, как часто встречаются показатели в заданных интервалах значений.

Функция ЧАСТОТА рабочего листа анализа MS Excel относится к категории статистических функций и возвращает распределение частот в виде вертикального массива. Для данного множества значений и заданного множества карманов (интервалов) частотное распределение подсчитывает, сколько значений попадает в каждый интервал.

В качестве массива данных может быть одномерный или двумерный массив (например, A 4: D 15).

Синтаксис: ЧАСТОТА (массив_данных; массив_карманов)

Для частотного анализа можно использовать команду Сервис/Анализ данных. Анализ данных является одной из надстроек Excel . Если в меню отсутствует эта команда, то следует выполнить команду Сервис/ Надстройки и установить соответствующий флажок в окне Надстройки .

Задание 1

С помощью функции Частота для выборки множества сумм заказов () введите в диапазон подсчитайте, сколько значений попадают в заданные интервалы значений. Например, от 0 до 1000, от 1001 до 1500, от 1501 до 2000, от 2001 до 2500, свыше 2500.

Порядок действий :

1. На рабочем листе MS Excel введите данные об объемах заказов в 20 филиалах фирмы за сентябрь в виде таблицы, фрагмент которой показан на рисунке.

1. В свободный диапазон клеток (столбец) введите верхние границы интервалов (Например, D 2=1000, D 3=1500, D 4=2000, D 5=2500).
2. Выделите блок ячеек столбца, смежного со столбцом интервалов (E 2: E 21). Для того, чтобы подсчитать количество значений, превышающих нижнюю границу интервала, выделяется диапазон, на одну ячейку больше, чем диапазон интервалов.
3. В диапазон E 2: E 6 введите формулу { =ЧАСТОТА(E 2: E 15; J 2: J 6)}.

Для этого воспользуйтесь мастером функций (Вставка/ Функция). В категории «Статистические» выберите из списка функцию «Частота». В диалоговом окне функции ЧАСТОТА заполните поля массива выборки и массива интервалов (рисунок 1). Не выходя из окна диалога нажмите комбинацию клавиш < Ctrl / Shift / Enter > для расчета элементов массива.

Рисунок 1 – Пример заполнения диалогового окна функции Частота.

1. Постройте диаграмму по полученным результатам.
2. Сохраните файл.

Задание 2

Создайте на рабочем листе двумерный массив, содержащий статистические данные о росте людей различных возрастных категорий. Проведите частотный анализ результатов с помощью функции ЧАСТОТА и Анализа данных (пункт меню Анализ данных/ Гистограмма) .

При использовании инструмента анализа данных в диалоговом окне в поле Входной интервал введите исходный интервал по которому строится гистограмма, в поле Интервал карманов - диапазон со значениями верхних границ интервалов. Гистограмма строится на новом или на текущем рабочем листе.

Часть 2

Решение задач прогнозирования в среде MS Excel . Метод скользящего среднего

Цель работы : Приобрести навыки прогнозирования экономической деятельности предприятия с применением статистического программного пакета MS Excel.

Краткая теория

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

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

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

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

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

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

Рассмотрим возможности прогнозирования показателей деятельности предприятия, занимающихся предоставлением услуг связи.

Задание к лабораторной работе (часть 2)

Задание 1 : Вычислить прогнозируемое значение величины объема продукции (услуг) предприятия методом скользящего среднего.

Порядок выполнения задания:

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

Для вычислений воспользуемся способом прямого введения формулы. Чтобы получить трехлетнее скользящее среднее объема выполненных услуг для нашего примера, введем в ячейку B 5 формулу для вычисления =СРЗНАЧ(A 2: A 4). Скопируем формулу в интервал B 6: B 11.

Рисунок 1 – Вычисление простого скользящего среднего

Проиллюстрируем результаты графиком, отражающим динамику изменения исходных данных и скользящего среднего.

Рисунок 2 – График тенденции изменения показателя объема услуг, полученной методом простого скользящего среднего

Другим способом решения является использование для определения скользящего целого Пакета анализа . Пакет анализа является надстройкой MS Excel (выберите пункт меню Сервис/ Надстройки и установите флажок Пакет анализа ).

Порядок действий

1. Выполнить команду Сервис/Анализ данных и выбрать из списка инструментов анализа Скользящее среднее.
2. В диалоговом окне укажите параметры для вычисления скользящего среднего:

• В качестве входного интервала выделите блок ячеек, содержащий данные об объеме услуг.
• Укажите Интервал- 3 (по умолчанию используется 3), в качестве выходного интервала – любую ячейку рабочего листа (просто щелкните на ячейке рабочего листа, с которой должны выводиться результаты);

Excel сам выполнит работу по внесению значений в формулу для вычислений скользящего среднего. Из-за недостаточного количества данных при вычислении среднего значения для первых результатов наблюдений в начальных ячейках выходного диапазона будет выведено значение ошибки #Н/Д. Учтите, что первое полученное значение ряда является прогнозным не на третий, а на четвертый период. Поэтому, если указанная для вывода ячейка соответствует началу столбца наблюдений, то нужно столбец рассчитанных значений переместить вниз на одну ячейку. Это действие присоединит прогнозы именно к тем периодам, для которых они рассчитаны.

Проанализируйте используемые расчетные формулы и полученные результаты.

Аналогично вычислите пятилетние простые скользящие средние. Сравните результаты сглаживания для двух вариантов расчета.

Задание 2: Вычислить прогнозируемое значение величины объема продукции (услуг) предприятия методом экспоненциального сглаживания.

Порядок действий:

1. На листе MS Excel создайте список, содержащий данные о численности сотрудников фирмы за последние 10 лет. Данные введите произвольно, но так, чтобы прослеживалась тенденция.
2. Проведите сглаживание временного ряда с использованием экспоненциальной средней с параметрами сглаживания 0,1 и затем 0,3. По результатам расчетов постройте график и определите, какой из полученных временных рядов носит более гладкий характер.

Воспользуйтесь командой Сервис/Анализ данных и выберите из списка инструментов анализа Экспоненциальное сглаживание. Укажите параметры для вычисления скользящего среднего:

• В качестве входного интервала выделите блок ячеек, содержащий данные о численности.
• Укажите Фактор затухания . В качестве выходного интервала – любую ячейку рабочего листа.
• Задайте вывод графика и стандартных погрешностей.

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

Часть 3

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

Краткая теория

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

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

Excel проводит линейную экстраполяцию, т.е. рассчитывает наиболее подходящую прямую, которая проходит через серию заданных точек. Задача заключается в нанесении на график набора точек, а затем в подборе линии, по которой можно проследить развитие функции с наименьшей ошибкой. Эта линия называется линией ТРЕНДА. Пользователь может использовать результат вычислений для анализа тенденций и краткосрочного прогнозирования.

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

• С помощью маркера заполнения
• С помощью функций рабочего листа

Первый способ

Линейное приближение

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

Экспоненциальное приближение

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

Второй способ

В MS Excel встроены статистические функции рабочего листа.

ТЕНДЕНЦИЯ() - возвращает значения в соответствии с линейной аппроксимацией по методу наименьших квадратов.

РОСТ() - возвращает значения в соответствии с экспоненциальным трендом.

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

Формат

ТЕНДЕНЦИЯ (изв_знач_Y; изв_знач_X; нов_знач_X; константа)

Функция РОСТ возвращает значения в соответствии с экспоненциальным трендом.

Задание к лабораторной работе (часть 3)

Задание 1:

Рассчитайте линейный и экспоненциальный прогноз на один год и на последующие три периода (до 2011 года) с помощью маркера заполнения.

Задание 2:

Рассчитайте линейный и экспоненциальный прогноз на один год и затем на последующие три периода с помощью функций рабочего листа ТЕНДЕНЦИЯ и РОСТ. Для расчета интервального прогноза после заполнения параметров диалогового окна функции и не выходя из него нажмите комбинацию клавиш Ctrl/ Shift/ Enter.

В строке формул рабочего листа должна появиться формула для расчета элементов массива, например,

{ = ТЕНДЕНЦИЯ (B 3: G 3; B 2: G 2; B 2: H 2)}

Определите, какая модель является наиболее точной.

Постройте графики и линии тренда для первого и второго задания.

В прошлом параграфе мы подчеркнули, что введенная там матрица смежности $A$, точнее матрица вершинной смежности графа, играет весьма существенную роль в теории графов. Мы отметили в качестве преимуществ этой матрицы — она квадратная порядка, равного числу строк матрицы инцидентности $B$, т.е., как правило, содержит меньшее число элементов. Во-вторых, эта матрица сохраняет всю информацию о ребрах графа и, при заданной нумерации вершин, однозначно описывает граф. Матрица смежности, как и матрица инцидентности графа, является (0,1)-матрицей, т.е. её элементы можно рассматривать как элементы других алгебраических структур, а не только как элементы множества целых чисел. В частности мы отметили, что элементы матрицы смежности могут рассматриваться как элементы булевой алгебры, подчиненные законам булевой арифметики, но не пояснили это должным образом. Прежде чем восполнить этот пробел, подчеркнем преимущества матрицы смежности, вытекающие из её квадратности.

Для этого напомним правила умножения матриц. Пусть даны произвольные матрицы с числовыми элементами: матрица $A$ размерности $n\times m$ с элементами $a_{ik}$ и матрица $B$ размерности $m\times q$ с элементами $b_{kj}$. Матрица $C$ размерности $n\times q$ называется произведением матрицы $A$ на $B$ (порядок важен), если её элементы $c_{ij}$ определяются следующим образом: $c_{ij} = \sum\limits_{k = 1}^m {a_{ik} b_{kj}}$. Произведение матриц записывается обычным образом $AB=C$. Как видим, произведение матриц требует согласованности размеров первого и второго сомножителей (число столбцов первой матрицы-сомножителя равно числу строк второй матрицы-сомножителя). Это требование отпадает, если рассматривать квадратные матрицы одного порядка и, следовательно, можно рассматривать произвольные степени квадратной матрицы. Это одно из преимуществ квадратных матриц перед прямоугольными. Другое преимущество состоит в том, что мы можем дать графовую интерпретацию элементам степеней матрицы смежности.

Пусть матрица смежности $A$ имеет вид: $A = \left({{\begin{array}{*c} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & {...} & {a_{2n} } \\ {...} & {...} & {...} & {...} \\ {a_{n1} } & {a_{n2} } & {...} & {a_{nn} } \\ \end{array} }} \right)$, а её $k$-ая степень — $A^k = \left({{\begin{array}{*c} {a_{11}^{(k)} } & {a_{12}^{(k)} } & {...} & {a_{1n}^{(k)} } \\ {a_{21}^{(k)} } & {a_{22}^{(k)} } & {...} & {a_{2n}^{(k)} } \\ {...} & {...} & {...} & {...} \\ {a_{n1}^{(k)} } & {a_{n2}^{(k)} } & {...} & {a_{nn}^{(k)} } \\ \end{array} }} \right)$, где $k = 2,3,...$ Очевидно, что $A^k$, как и матрица $A$ будет симметричной матрицей.

Пусть $k=2$. Тогда $a_{ij}^{(2)} = \sum\limits_{k = 1}^n {a_{il} a_{lj}}$ ($i,j = 1,2,...,n$), и каждое слагаемое $a_{il} a_{lj}$ равно либо $0$, либо $1$. Случай, когда $a_{il} a_{lj} = 1$ означает, что в графе существуют два ребра: ребро $\{i,l\}$ (поскольку $a_{il} = 1)$ и ребро $\{l,j\}$ (поскольку $a_{lj} = 1$) и, следовательно, путь $\{{ \{i,l\}, \{l,j\} }\}$ из $i$-ой вершины в $j$-ую длиной два (путь из двух ребер). Здесь речь идет именно о пути, а не цепи, поскольку указано направление — из из $i$-ой вершины в $j$-ую. Таким образом, $a_{ij}^{(2)}$ дает нам количество всех путей на графе (в геометрической интерпретации графа) длины 2, ведущих из $i$-ой вершины в $j$-ую.

Если $k=3$, то $A^3 = A^2A = AA^2 = AAA$ и $a_{ij}^{(3)} = \sum\limits_{l_1 = 1}^n {a_{il_1 } } a_{l_1 j}^{(2)} = $ $\sum\limits_{l_1 = 1}^n {a_{il_1 } } \left({\sum\limits_{l_2 = 1}^n {a_{l_1 l_2 } a_{l_2 j} } } \right) =$ $\sum\limits_{l_1 = 1}^n {\sum\limits_{l_2 = 1}^n {a_{il_1 } } } a_{l_1 l_2 } a_{l_2 j} = \sum\limits_{l_1 ,l_2 = 1}^n {a_{il_1 } a_{l_1 l_2 } a_{l_2 j} }$.

Слагаемое $a_{il_1 } a_{l_1 l_2 } a_{l_2 j} $ в случае если оно равно 1, определяет путь длины 3 идущий из $i$-ой вершины в $j$-ую и проходящий через вершины $l_1$ и $l_2$. Тогда $a_{ij}^{(3)}$ дает нам количество путей длины 3, соединяющих $i$-ую и $j$-ую вершины. В общем случае $a_{ij}^{(k)}$ задает количество путей длины $k$, соединяющих $i$-ую и $j$-ую вершины. При этом $a_{ij}^{(k)} = \sum\limits_{l_1 ,l_2 ,...,l_{k - 1} = 1}^n {a_{il_1 } a_{l_1 l_2 } ...} a_{l_{k - 2} l_{k - 1} } a_{l_{k - 1} j}$.

Ясно, что величина $a_{ii}^{(k)} $ дает нам количество замкнутых путей длины $k$, начинающихся и оканчивающихся в вершине $i$. Так, путь длины 2 — $a_{il} a_{li}$, означает путь, проходящий по ребру $\{ i,l \}$ из вершины $i$ в вершину $l$ и обратно. Поэтому $a_{ii}^{(2)} = s_i$, т.е. диагональные элементы матрицы $A^2$ равны степеням соответствующих вершин.

Рассмотрим теперь наряду с матрицей $A$ матрицу $\dot {A}$, которая отличается от матрицы $A$ только тем, что у неё элементы (числа 0 или 1) рассматриваются как элементы булевой алгебры. Поэтому действия с такими матрицами будут проводиться по правилам булевой алгебры. Поскольку действия сложения и умножения матриц с булевыми элементами сводится к действиям сложения и умножения элементов этих матриц по правилам булевой арифметики, то, надеемся, что это не приведет к затруднениям. Матрицу с булевыми элементами будем называть булевой матрицей. Очевидно, что операции сложения и умножения булевых матриц замкнуты на множестве булевых матриц, т.е. результат этих операций будет снова булевой матрицей.

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

Результатом сложения двух булевых симметричных матриц одного порядка будет булева симметричная матрица того же порядка с нулями на тех местах, на которых у обоих слагаемых стоят нули и единицами на тех местах, на которых по крайней мере у одного слагаемого стоит единица. В графовой интерпретации эта операция называется операцией сложения графов . Суммой двух графов , заданных на одном и том же множестве вершин с одной и той же их нумерацией, называется граф, у которого вершины i и j несмежные, если они несмежные у обоих графов-слагаемых, и вершины i и j смежные, если они смежные хотя бы у одного графа-слагаемого .

Проинтерпретируем теперь вторую степень булевой матрицы смежности $\dot {A}^2$ с элементами $\dot {a}_{ij}^{(2)} = \sum\limits_{l = 1}^n {\dot {a}_{il} \dot {a}_{lj} }$. Ясно, что $\dot {a}_{ij}^{(2)} = 1$, если хотя бы одно слагаемое $\dot {a}_{il} \dot {a}_{lj} $ равно 1 и $\dot {a}_{ij}^{(2)} = 0$, если все слагаемые равны 0. Если матрица $\dot {A}$ является матрицей смежности некоторого графа, т.е. является симметричной (0,1)-матрицей с нулевой главной диагональю, то матрица $\dot {A}^2$, вообще говоря, не является матрицей смежности графа в принятом нами смысле, поскольку у неё все диагональные элементы равны 1 (если у графа нет изолированных вершин). Чтобы и на такие матрицы можно было смотреть как на матрицы смежности, мы должны при рассмотрении связей между вершинами некоторой связанной системы, определяющих эту систему как граф, допустить связь некоторых вершин самих с собой. «Ребро», определяющее связь некоторой вершины самой с собой называется петлей . Мы дальше, по-прежнему, под словом граф будем понимать граф без петель, а про граф с петлями, если это не будет ясно из контекста, так и будем говорить — граф с петлями.

Рассмотрим сумму $\dot {A}^{} = \dot {A} + \dot {A}^2$. Матрица $\dot {A}^{}$ задает нам граф, полученный из исходного «насыщением» его дополнительными связями, соответствующими путям длины 2. То есть в новом графе вершины $i$ и $j$ смежные, если они смежные в исходном графе или эти вершины связаны каким-нибудь путем длины 2, и вершины $i$ и $j$ несмежные, если они несмежные в исходном графе и не существует никакого пути длины 2, соединяющего эти вершины.

Аналогично определяется $\dot {A}^{} = \dot {A} + \dot {A}^2 + \dot {A}^3$. То есть в графе, заданном матрицей $\dot {A}^{}$ вершины $i$ и $j$ смежные, если они смежные в графе $\dot {A}^{}$ или эти вершины связаны каким-нибудь путем длины 3 в исходном графе, и вершины $i$ и $j$ несмежные, если они несмежные в графе $\dot {A}^{}$ и не существует никакого пути длины 3, связывающих эти вершины в исходном графе. И так далее.

В общем случае $\dot {A}^{[k]} = \sum\limits_{i = 1}^k {\dot {A}^i} $. Нетрудно видеть, что все $\dot {A}^{[k]}$ при $k \ge n - 1$, где $n$ — порядок матрицы $\dot {A}$, равны между собой. Действительно, если вершины $i$ и $j$ связны, то существует путь (цепь) связывающий эти вершины, а, следовательно, существует простой путь (простая цепь) связывающий эти вершины. Максимальная возможная простая цепь в $n$-вершинном графе имеет длину $n-1$ (простая цепь, связывающая все различные вершины графа). Поэтому, если в матрице $\dot {A}^{}$ на месте $(i,j)$ стоит 1, то на этом же месте в матрице $\dot {A}^{[k]}$ при $k \ge n - 1$ будет также стоять 1, поскольку матрица $\dot {A}^{}$ входит в качестве булева слагаемого в определение матрицы $\dot {A}^{[k]}$. Если же в матрице $\dot {A}^{}$ на месте $(i,j)$ стоит 0, то это значит, что в графе не существует никакой простой цепи, соединяющей $i$-ую и $j$-ую вершины, а, следовательно, не существует вообще никакой цепи связывающей эти вершины. Значит, в рассматриваемом случае и в матрице $\dot {A}^{[k]}$ при $k \ge n - 1$ на месте ($i$,$j)$ будет стоять 0. Что и доказывает наше утверждение о равенстве всех матриц $\dot {A}^{[k]}$ при $k \ge n - 1$ матрице $\dot {A}^{}$ и, следовательно, между собой.

Матрицу $\dot {A}^{}$ называют матрицей транзитивного замыкания матрицы $\dot {A}$, а также матрицей смежности транзитивного замыкания графа, заданного матрицей $\dot {A}$. Достаточно очевидно, что матрицей транзитивного замыкания связного графа будет матрица смежности полного графа, т.е. квадратная матрица, состоящая из одних единиц. Это наблюдение дает нам и метод определения связности графа: граф связный тогда и только тогда, когда матрица транзитивного замыкания его матрицы смежности будет состоять из одних единиц (будет матрицей полного графа) .

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

Покажем теперь, как процедура транзитивного замыкания позволяет построить так называемую «матрицу расстояний». Для этого определим расстояние между вершинами $i$ и $j$. Если вершины $i$ и $j$ связные, то расстоянием между ними назовем длину минимального (по числу обхода ребер) простого пути, связывающего эти вершины; если вершины $i$ и $j$ несвязные, то положим расстояние равным нулю (ноль как отрицание какого-либо пути связывающего эти вершины). При таком определении расстояния расстояние между вершиной и ею же самой равно 2 (длина пути по ребру и обратно). Если же при вершине имеется петля, то расстояние между вершиной и ею же самой равно 1.

Для построения матрицы расстояний для $n$-вершинного графа с матрицей смежности $A$, которая указывала бы расстояние между любыми двумя вершинами, введем в рассмотрение матрицы $A^{\{k\}} = A^{[k]} - A^{}$, где $k = 2,3,...,n - 1$ и $A^{\{1\}} = A^{} = A$. Отсутствие точек над обозначением матриц указывает, что мы рассматриваем матрицы $A^{[k]}$ ($k = 1,2,...,n - 1)$ как числовые (0,1)-матрицы, естественным образом получаемые из матриц $\dot {A}^{[k]}$ (булевы элементы 0 и 1 мы теперь рассматриваем как числа 0 и 1). Из способа построения матриц $A^{[k]}$ следует, что $A^{[k]} \ge A^{}$ ($k = 2,3,...,n - 1$) и, следовательно, $A^{\{k\}}$ ($k = 1,2,...,n - 1$) являются (0,1)-матрицами. Причем матрица $A^{\{2\}}$ содержит 1 только на тех местах, где определяемые этим местом (номер строки и номер столбца) вершины соединены некоторым путем длины два и не соединены меньшим путем. Аналогично, $A^{\{3\}}$ содержит 1 только на тех местах, где определяемые этим местом вершины соединены путем длины три и не соединены никаким путем меньшей длины, и т.д. Таким образом, матрица $D = \sum\limits_{k = 1}^{n - 1} {k \cdot A^{\{k\}}}$ и будет искомой матрицей расстояний. Элемент $d_{ij}$ этой матрицы и будет равен расстоянию между вершинами $i$ и $j$. Расстояние между вершинами $u$ и $v$ будем также обозначать как $d(u,v)$.

Замечание. Конкретное произведение-слагаемое $a_{il_1 } a_{l_1 l_2 } ...a_{l_{k - 2} l_{k - 1} } a_{l_{k - 1} j} = 1$ элемента $a_{ij}^{(k)}$ $k$-ой степени матрицы смежности $A^k$ задает конкретный $(i,j)$-путь $i\{i,l_1\}l_1 \{l_1 ,l_2 \}l_2 ...l_{k - 2} \{l_{k - 2} ,l_{k - 1} \}l_{k - 1} \{l_{k - 1} ,j\}j$ из $i$-ой вершины в $j$-ую. Последовательность смежных вершин и соединяющих их ребер $i\{i,l_1 \}l_1 \{l_1 ,l_2 \}l_2 ...l_{k - 2} \{l_{k - 2} ,l_{k - 1} \}l_{k - 1} \{l_{k - 1} ,j\}j$ называют ещё $(i,j)$-маршрутом . Маршрут отличается от цепи, состоящей только из различных смежных ребер, ещё тем, что в маршруте допускаются равные ребра. Простой маршрут состоит из различных смежных вершин и ребер, т.е. практически совпадает с простой цепью.

Достаточно очевидно, что элемент $d_{ij} $ матрицы расстояний определяет длину минимальной цепи соединяющей $i$-ую вершину с $j$-ой.

Рассмотрим примеры графов, заданных рисунками 1 и 2, их матриц смежности и их матриц расстояний.

Рис.1 (Граф $\Gamma _1$, матрица смежности $A_1$, матрица расстояний $D_1$).
$A_1 = \left({{\begin{array}{*c} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end{array} }} \right), $
$D_1 = \left({{\begin{array}{*c} 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end{array} }} \right) $

Рис. 2 (Граф $\Gamma _2$, матрица смежности $A_2$, матрица расстояний $D_2$).
$A_2 = \left({{\begin{array}{*c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{array} }} \right)$,
$D_2 = \left({{\begin{array}{*c} 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & 3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 \\ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end{array} }} \right). $

По матрицам $D_1$ и $D_2$ легко определяются диаметры $d_1$ графа $\Gamma _1$ и $d_2$ графа $\Gamma _2$, как максимальные значения элементов этих матриц. Так $d_1 = 3$, а $d_2 = 6$.

Кроме матрицы расстояний теория графов рассматривает и другие матрицы, элементы которых определяются через длину пути. Таковой, например, является матрица обходов . В матрице обходов $(i,j)$-й элемент равен длине наиболее длинного пути (наиболее длинной цепи) из $i$-ой вершины в $j$-ую, а если таких путей нет вообще, то в соответствии с определением расстояния $(i,j)$-ый элемент матрицы обходов полагается равным нулю.

О методах определения минимальной и максимальной цепей с использованием матрицы расстояний, соединяющих $i$-ую и $j$-ую вершины в графе, сделаем замечание в конце параграфа.

А сейчас приведем ещё некоторые определения теории графов, связанные с расстояниями между вершинами и которые легко определяются из матриц расстояний.

Эксцентриситет $e(v)$ вершины $v$ в связном графе $\Gamma$ определяется как max $d(u,v)$ по всем вершинам $u$ в $\Gamma$. Радиусом $r(\Gamma)$ называется наименьший из эксцентриситетов вершин. Заметим, что наибольший из эксцентриситетов равен диаметру графа. Вершина $v$ называется центральной вершиной графа $\Gamma$, если $e(v) = r(\Gamma)$; центр графа $\Gamma$ — множество всех центральных вершин.

Так для графа $\Gamma _1$ с рис.1, эксцентриситет вершины 13 будет равен 2 ($e(13) = 2$). Такие же эксцентриситеты будут иметь вершины 3, 5 и 10 ($e(3) = e(5) = e(10) = 2$). Эксцентриситет равный 2 будет наименьшим для графа $\Gamma _1$, т.е. $r(\Gamma _1) = 2$. Центр графа $\Gamma _1$ будет состоять из вершин 3, 5, 10 и 13. Наибольший эксцентриситет будет равен 3 и будет равен, как отмечалось выше, диаметру графа $\Gamma _1$.

Для графа $\Gamma _2$ с рис. 2 наименьший эксцентриситет будет иметь единственная вершина 4 ($e(4) = r(\Gamma _2) = 3$). Следовательно, центр графа $\Gamma _2$ состоит из одной вершины 4. Диаметр графа $\Gamma _2$, как отмечалось выше, равен 6.

Граф $\Gamma _2$ является деревом, а структуру центра любого дерева описывает приводимая ниже теорема.

Теорема Жордана—Сильвестра. Каждое дерево имеет центр, состоящий или из одной вершины или двух смежных вершин.

Доказательство. Обозначим через $K_1$ граф, состоящий из одной изолированной вершины, а через $K_2$ — граф — из двух вершин соединенных ребром. По определению положим $e(K_1) = r(K_1) = 0$. Тогда утверждение теоремы будет выполнено для $K_1$ и $K_2$. Покажем, что у любого дерева $T$ те же центральные вершины, что и у дерева ${T}"$, полученного из $T$ удалением всех его висячих вершин. Ясно, что расстояние от данной вершины $u$ до любой другой вершины $v$ может достигать наибольшего значения только тогда, когда $v$ — висячая вершина.

Таким образом, эксцентриситет каждой вершины дерева ${T}"$ точно на единицу меньше эксцентриситета этой же вершины в $T$. Отсюда вытекает, что вершины дерева $T$, имеющие наименьший эксцентриситет в $T$, совпадают с вершинами, имеющими наименьший эксцентриситет в ${T}"$, т.е. центры деревьев $T$ и ${T}"$ совпадают. Если процесс удаления висячих вершин продолжить, то мы получим последовательность деревьев с тем же центром, что и у $T$. В силу конечности $T$ мы обязательно придем или к $K_1$, или к $K_2$. В любом случае все вершины дерева полученного таким способом, образуют центр дерева, который, таким образом, состоит или из единственной вершины, или из двух смежных вершин. Доказательство закончено.

Покажем теперь, как с помощью матрицы расстояний можно определить, например, минимальную цепь соединяющую вершину 4 с вершиной 8 на графе $\Gamma _1$. В матрице $D_1$ элемент $d_{48} = 3$. Возьмем 8-ой столбец матрицы $D_1$ и найдем в столбце все элементы этого столбца равные 1. По крайней мере, один такой элемент найдется в силу связности графа $D_1$. На самом деле таких единиц в 8-ом столбце будет три, и расположены они в 5-ой, 6-ой и 7-ой строках. Возьмем теперь 4-ую строку и рассмотрим в ней элементы, расположенные в 5-ом, 6-ом и 7-ом столбцах. Эти элементы будут 2, 3 и 3 соответственно. Только элемент, расположенный в 5-ом столбце равен 2 и вместе с 1, расположенной на месте (5,8), дает сумму 3. Значит, вершина 5 входит в цепь $\{ \{4,?\}, \{?,5\}, \{5,8\} \}$. Возьмем теперь 5-ый столбец матрицы и рассмотрим 1 этого столбца. Это будут элементы расположенные в 3-ей, 6-й, 7-ой, 8-ой, 10-ой и 13-ой строках. Вновь возвращаемся к 4-ой строке и видим, что только на пересечении третьего столбца и 4-й строки стоит 1, что в сочетании с 1 на месте (3,5) дает в сумме 2. Следовательно, искомая цепь будет $\{ \{4,3\}, \{3,5\}, \{5,8\} \}$. Посмотрев теперь на рисунок 1, убеждаемся в справедливости найденного решения.

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

Утверждение. Если для двух вершин существует маршрут, связывающий их, то обязательно найдется минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута через d(v, w).

Определение. Величину d(v, w) (конечную или бесконечную) будем называть расстоянием между вершинами v, w . Это расстояние удовлетворяет аксиомам метрики:

1) d(v, w) 0, причем d(v, w) = 0 тогда и только тогда, когда v= w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

Определение. Диаметром связного графа называется максимально возможное расстояние между двумя его вершинами.

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

Пример 82.

Для графа G, изображенного на рис. 3.16, найти радиус, диаметр и центры.

Рис. 3.16. Граф для примера 82

Решение.

Чтобы определить центры, радиус, диаметр графа G , найдем матрицу D(G) расстояний между вершинами графа, элементами d ij которой будут расстояния между вершинами v i и v j . Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали.

С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5 . В результате получаем: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3. Минимальное из полученных чисел является радиусом графа G , максимальное – диаметром графа G . Значит, R(G) = 2 и D(G) = 3 , центрами являются вершины v 2 , v 3 , v 4 .

Граф – это совокупность двух множеств: вершини ребер, между которыми определено отношениеинцидентности .

Каждое ребро e из E инцидентно ровно двум вершинам и, которые оно соединяет. При этом вершинаи реброe называются инцидентными друг другу, а вершины иназываютсясмежными .

Принято обозначение n для числа вершин графа (мощность множества ):
иm для числа его ребер:
. Говорят, что графG есть (n , m ) граф, где n – порядок графа, m – размер графа.

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

Маршрут – последовательность ребер, в которой каждые два соседних ребра имеют общую вершину. Граф связен , если любые две вершины соединены хотя бы одним маршрутом. Число ребер маршрута определяет его длину.

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

Ребро
называетсяпетлей (концевые вершины совпадают). Граф, содержащий петли и кратные ребра, называется псевдографом . На рис. 12.2 показан псевдограф.

Степень deg(v ) вершины – это число ребер, инцидентных v . В неографе сумма степеней всех вершин равна удвоенному числу ребер (лемма о рукопожатиях):

. (12.1)

Петля дает вклад, равный 2, в степень вершины.

Степенная последовательность – последовательность степеней всех вершин графа, записанная в определенном порядке (по возрастанию или убыванию).

Пример 12.1. Степенная последовательность неографа, изображенного на рис. 12.1, записанная по возрастанию, выглядит так:

=1,
=2,
=3,
=3,
=3.

Сумма степеней всех вершин графа равна:

.

Этот результат не противоречит лемме о рукопожатиях, поскольку граф имеет шесть ребер (m = 6).

Матрица смежности графа – квадратная матрица A порядка n , где элемент равен числу ребер, соединяющих вершиныi и j .

Пример 12.2. Граф, показанный на рис. 12.1, имеет следующую матрицу смежности

.

Матрица инцидентности I – еще один способ описания графа. Число строк этой матрицы равно числу вершин, число столбцов – числу ребер; =1, если вершинаv инцидентна ребру e ; в противном случае =0. В каждом столбце матрицы инцидентности простого графа (без петель и без кратных ребер) содержится по две единицы. Число единиц в строке равно степени соответствующей вершины.

Пример 12.3. Граф, показанный на рис. 12.1, имеет следующую матрицу инцидентности

.

Граф
называетсяподграфом графа
, если
и
. Если
, то подграф называетсяостовным .

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

Ранг графа
, гдеk – число компонент связности.

Дерево – связной граф, содержащий n – 1 ребро.

Пример 12.4. На рис. 12.3 показано дерево, которое одновременно является остовным подграфом графа, показанного на рис. 12.1.

Радиус, диаметр и центр графа

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

Эксцентриситет вершины графа – расстояние до максимально удаленной от нее вершины. Для графа, для которого не определен вес его ребер, расстояние определяется в виде числа ребер.

Радиус графа – минимальный эксцентриситет вершин, а диаметр графа – максимальный эксцентриситет вершин.

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

Периферийные вершины имеют эксцентриситет, равный диаметру.

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

Теорема 12.1. В связном графе диаметр не больше ранга его матрицы смежности.

Теорема 12.2. (Жордана) Каждое дерево имеет центр, состоящий из одной или двух смежных вершин.

Теорема 12.3. Если диаметр дерева четный, то дерево имеет единственный центр, и все диаметральные цепи проходят через него, если диаметр нечетный, то центров два и все диаметральные цепи содержат ребро, их соединяющее.

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

Пример 12.5. Найти радиус, диаметр и центр графа, изображенного на рис. 12.1.

Решение. В данной задаче удобно использовать матрицу расстояний S . Элемент этой квадратной симметричной матрицы равен расстоянию между вершинойi и вершиной j . Для графа, показанного на рис. 12.1, матрица расстояний имеет следующий вид:

. (12.2)

Вычислим эксцентриситет каждой вершины. Эту величину можно определить как максимальный элемент соответствующего столбца матрицы расстояний (или строки – поскольку матрицаS симметрична). Получаем

Радиус графа r – минимальный эксцентриситет вершин. В данном случае r = 2. Такой эксцентриситет имеют вершины № 2, № 4 и № 5. Эти вершины образуют центр графа. Диаметр графа d – максимальный эксцентриситет вершин. В данном случае d = 3. Такой эксцентриситет имеют вершины № 1 и № 3, это периферия графа. В исследованном графе вершины оказались либо центральными, либо периферийными. В графах большего порядка существуют и другие вершины.

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

Теорема 12.4. Пусть
– матрица смежности графа G без петель и
, где
. Тогдаравно числу маршрутов длины k от вершины к вершине.

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

Пример 12.6. Найти матрицу расстояний графа, изображенного на рис. 12.1, алгебраическим методом.

Решение. Матрица смежности данного графа равна:

.

Будем заполнять матрицу расстояний, рассматривая степени матрицы смежности. Единицы матрицы смежности показывают пары вершин, расстояние между которыми равно единице (т.е. они соединены одним ребром).

.

Диагональные элементы матрицы расстояний – нули. Умножаем матрицу смежности на себя:

.

Согласно теореме между вершинами 2 и 3, 1 и 4 и т.д. имеется некоторое число маршрутов длиной 2 (поскольку степень матрицы равна двум). Число маршрутов здесь не используется, важен сам факт наличия маршрута и его длина, на что и указывает ненулевой элемент степени матрицы, не совпадающий с элементом, отмеченным при вычислении маршрута меньшей длины. Проставляем 2 в незаполненные элементы матрицы расстояний и получаем следующее приближение:

.

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

,

следовательно,
, и окончательно

.

Полученная матрица совпадает с матрицей расстояний S (12.2), найденной непосредственными вычислениями по рисунку.

Эйлерова цепь

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

Рис. 12.4. Схема Кенигсбергских мостов

Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач. В их ряду – знаменитый математик Леонард Эйлер (1707-1783). К созданию теории графов его подтолкнула задача о Кенигсберских мостах, которую он решил в 1736 году. По условию задачи требовалось пройти по всем семи мостам города Кенигсберга через реку Преголь по одному разу и вернуться к исходной точке. На рис. 12.4 показана схема этих мостов (один из них соединяет между собой два острова, а остальные – острова с берегами). Этой схеме соответствует приведенный на следующем рисунке мультиграф с четырьмя вершинами.

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

Теорема 12.5 (Эйлера). Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2.

Вершины нечетной степени в этой теореме, очевидно, являются началом и концом цепи. Если таких вершин нет, то эйлерова цепь становится эйлеровым циклом . Граф, обладающий эйлеровым циклом, называется эйлеровым . Если граф имеет эйлерову цепь, но не обладает эйлеровым циклом (число вершин нечетной степени равно 2), то он называется полуэйлеровым графом.

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

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

Рассмотрим для сравнения граф, обладающий эйлеровой цепью. В графе на рис. 12.6 только две вершины имеют нечетную степень, следовательно, эйлерова цепь есть.

Цепей может быть несколько. Например, граф на рис. 12.6 имеет две эйлеровы цепи: 1-2-3-4-1-3 и 1-2-3-1-4-3.

Реберный граф

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

Английское название реберного графа – line graph , отсюда и обозначение графа – L (G ) . На рис. 12.7 показан реберный граф (он выделен жирными линиями), построенный для графа с рис. 12.1.

Рис. 12.7. Реберный граф

Теорема 12.6. Если
– степенная последовательность (n , m ) графа G , то L (G ) является (m , )-графом, где

. (12.3)

Для графа G , показанного на рис. 12.7 (и рис. 12.1), его степенная последовательность: 1-3-2-3-3. Поэтому

Раскраска графа, хроматический полином

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

Упростим задачу. Будем использовать меньшее количество красок, но при этом не будем допускать, чтобы соседние страны, имеющие общие границы, были окрашены в один цвет. Возникает вопрос: какое минимальное количество красок требуется, чтобы удовлетворить этому условию?

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

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

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

Теорема 12.7 (Брукса). Для любого графа G , не являющегося полным,
, если
–максимальная из степеней вершин графа .

Для определения количества способов раскраски графа в x цветов, необходимо составить хроматический полином P (G , x ). Значение полинома при некотором конкретном
равно числу правильных раскрасок графа вцветов.

Существует лемма, утверждающая, что хроматический полином графа имеет вид

, (12.4)

где – граф, полученный из G добавлением ребра (u , v ), а граф получается из G отождествлением вершин u и v .

Другой вариант леммы:

где – граф, полученный из G удалением ребра (u , v ), а граф получается из G отождествлением вершин u и v .

Операцию отождествления вершин u и v называют также стягиванием ребра (u , v ).

Оба варианта леммы составляют основу для хроматической редукции графа (reduction – «сокращение» на английском). Хроматическая редукция графа – представление графа в виде нескольких пустых или полных графов, сумма хроматических полиномов которых равна хроматическому полиному графа. Очевидно, что хроматический полином пустого графа равен(каждая вершина может быть раскрашена независимо от других), а для полного графа. Последнее выражение называютфакториальной степенью переменной x :
.

Разложения по пустым и полным графам связаны. Факториальную степень можно представить в виде полинома:

, (12.6)

где
– числа Стирлинга первого рода. И наоборот, степеньможно выразить через факториальные степени:

, (12.7)

где
– числа Стирлинга второго рода, обладающие следующими свойствами:

при
, (12.8)

при
,
при
.

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

Теорема 12.8. Коэффициенты хроматического полинома составляют знакопеременную последовательность .

Теорема 12.9. Абсолютная величина второго коэффициента хроматического полинома равна числу ребер графа.

Теорема 12.10. Наименьшее число i , для которого отличен от нуля коэффициент при в хроматическом полиноме графа G , равно числу компонент связности графа G .

Кроме вершинной раскраски, существует еще реберная раскраска и раскраска граней.

Пример 12.7. Найти хроматический полином графа, показанного на рис. 12.8.

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

1. Хроматическая редукция по пустым графам . Воспользуемся вначале леммой (12.5). Удаляя ребра и отождествляя соответствующие вершины (стягивая ребра), сведем исходный граф к пустым графам. Сначала разложим граф на два, убрав, а затем стянув ребро 1-3. Выполненное действие запишем в виде условного равенства:

Здесь операция вычитания относится не к самому графу, а к его хроматическому полиному. Таким образом, последнее равенство означает, что . Для сокращения записи обозначениеP (…) будем опускать. Далее разложим каждый из графов и , пользуясь той же леммой.

Приведем подобные члены:

В итоге получим искомый хроматический полином:

Разложение (12.9) называется хроматической редукцией графа по пустым графам.

Очевидно, что результат соответствует утверждениям теорем 12.8-12.10. Коэффициенты в (12.10) образуют знакопеременную последовательность, а коэффициент при равен четырем – числу ребер. Наименьшая степеньx в полиноме равна 1, т.е. числу компонент связности графа.

2. Хроматическая редукция по полным графам . Добавив к изображенному на рис. 12.8 графу ребро 1–4, получим граф с большим числом ребер. Затем в исходном графе отождествим вершины 1 и 4. В результате получим два графа.

Отождествление вершин приводит к уменьшению порядка и иногда размера графа. Второй граф – это полный граф
, его преобразовывать больше не требуется. К первому графу добавим ребро 1–2 и отождествим вершины 1 и 2:

В итоге получим

(12.11)

Хроматический полином примет вид

Разложение (12.11) называется хроматической редукцией графа по полным графам.

Оба способа дали один результат, и из редукции по полным графам легко получить редукцию по пустым. Для этого достаточно раскрыть скобки и привести подобные члены, как в (12.12). Однако обратное действие не очевидно. Для того чтобы полином , полученный из пустых графов, выразить в виде суммы факториальных степеней, необходимы числа Стирлинга 2-го рода. Согласно рекуррентным формулам (12.8) имеем следующие числа:

Пользуясь (12.7) и найденными числами Стирлинга 2-го рода, получим

,

Произведем преобразование хроматического полинома:

Хроматическое число
графа лучше всего получить, разложив хроматический полином на множители:

Минимальное натуральное число x , при котором
не обращается в нуль, равно 3. Отсюда следует
. Так как максимальная степень вершин графа
, выполняется оценка
.

Ранг-полином графа

Ранг графа определяется как
, гдеn – число вершин, k – число компонент связности графа. Коранг графа, или цикломатический ранг, есть , гдеm – число ребер.

Ранг-полином графа G имеет вид

,

где
– ранг графаG , а
– корангостовного (т.е. включающего в себя все вершины графа) подграфа H , а – его ранг. Суммирование ведется по всем остовным подграфам графаG .

Ранг полином служит для анализа множества остовных подграфов. Так, например, коэффициент при
в
есть число подграфов размераk , а значение
равно числу подграфов (включая несобственный подграф), ранг которых равен рангу самого графа.

Пример 12.8. Найти ранг-полином графа, изображенного на рис. 12.8.

Решение. Найдем все 16 остовных подграфов графа G (рис. 12.9). Множество представим в виде четырех графов размера 1 (т.е. с одним ребром), шести графов размера 2, четырех графов размера 3 и двух несобственных графов (пустой граф и граф G ).

Учитывая, что ранг графа равен 3, получаем сумму:

Циклы

Маршрут, в котором начало и конец совпадают, – циклический . Циклический маршрут называется циклом , если он – цепь.

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

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

Теорема 12.11. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому рангу графа.

Пример 12.8. По заданной матрице смежности:

,

определить число циклов длины 3 () и длины 4 (). Записатьматрицу фундаментальных циклов .

Решение. Матрица смежности данного графа симметричная, поэтому ей соответствует неориентированный граф. Сумма ненулевых элементов матрицы равна 12, следовательно, по лемме о рукопожатиях в графе 6 ребер. Построим этот граф (рис. 12.10). Очевидно, в нем два цикла (3–4–5 и 1–3–5) длиной 3 и один цикл (1–3–4–5) длиной 4. В данной задаче решение получено прямым подсчетом по изображению графа. Для более сложных случаев существует алгоритм решения задачи по матрице смежности.

Известно, что след (trace ) матрицы смежности, возведенный в k -ю степень, равен числу циклических маршрутов длины k (см. теорему 12.4). Это число включает в себя и искомое число циклов. Цикл отличается от циклического маршрута тем, что в нем не повторяются ребра. Кроме того, предполагается, что искомые циклы не помечены, а в след матрицы входят именно помеченные маршруты.

Непомеченных циклов длиной 3 в 6 раз меньше, чем помеченных, так как каждый помеченный цикл может отличаться началом (а их в данном случае три) и двумя направлениями обхода (по и против часовой стрелки). Возведем заданную матрицу смежности в третью степень:

,

и получим

.

Поскольку циклических маршрутов длиной 3, отличных от циклов длиной 3, не существует, найденное число и есть ответ в поставленной задаче.

С циклами длиной 4 немного сложнее. В след четвертой степени матрицы смежности графа

,

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

Легко заметить, что
. Число
зависит от степеней вершин, соседних с:

,

где
– ребро, инцидентное вершинамi и k .

Для графа на рис. 12.10 получим

,

С учетом того, что непомеченных циклов длиной 4 в 8 раз меньше, получим

После преобразований формула примет вид

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

Двум хордам, 1 и 2, соответствуют два фундаментальных цикла: 1–4–5 и 2–4–6 (рис. 12.11 (б и в)). Матрица фундаментальных циклов имеет две строки (число циклов) и шесть столбцов (число ребер).

В первой строке матрицы единицами отмечены столбцы с номерами ребер, входящих в первый цикл, а во второй строке – номера ребер из второго цикла.

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

Эксцентриситет вершины графа – расстояние до максимально удаленной от нее вершины. Для графа, для которого не определен вес его ребер, расстояние определяется в виде числа ребер.

Радиус графа – минимальный эксцентриситет вершин, а диаметр графа – максимальный эксцентриситет вершин.

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

Периферийные вершины имеют эксцентриситет, равный диаметру.

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

Теорема 12.1. В связном графе диаметр не больше ранга его матрицы смежности.

Теорема 12.2. (Жордана) Каждое дерево имеет центр, состоящий из одной или двух смежных вершин.

Теорема 12.3. Если диаметр дерева четный, то дерево имеет единственный центр, и все диаметральные цепи проходят через него, если диаметр нечетный, то центров два и все диаметральные цепи содержат ребро, их соединяющее.

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

Пример 12.5. Найти радиус, диаметр и центр графа, изображенного на рис. 12.1.

Решение. В данной задаче удобно использовать матрицу расстояний S . Элемент этой квадратной симметричной матрицы равен расстоянию между вершиной i и вершиной j . Для графа, показанного на рис. 12.1, матрица расстояний имеет следующий вид:

. (12.2)

Вычислим эксцентриситет каждой вершины. Эту величину можно определить как максимальный элемент соответствующего столбца матрицы расстояний (или строки – поскольку матрица S симметрична). Получаем

Радиус графа r – минимальный эксцентриситет вершин. В данном случае r = 2. Такой эксцентриситет имеют вершины № 2, № 4 и № 5. Эти вершины образуют центр графа. Диаметр графа d – максимальный эксцентриситет вершин. В данном случае d = 3. Такой эксцентриситет имеют вершины № 1 и № 3, это периферия графа. В исследованном графе вершины оказались либо центральными, либо периферийными. В графах большего порядка существуют и другие вершины.

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

Теорема 12.4. Пусть – матрица смежности графа G без петель и , где . Тогда равно числу маршрутов длины k от вершины к вершине .

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

Пример 12.6. Найти матрицу расстояний графа, изображенного на рис. 12.1, алгебраическим методом.

Решение. Матрица смежности данного графа равна:

.

Будем заполнять матрицу расстояний, рассматривая степени матрицы смежности. Единицы матрицы смежности показывают пары вершин, расстояние между которыми равно единице (т.е. они соединены одним ребром).

.

Диагональные элементы матрицы расстояний – нули. Умножаем матрицу смежности на себя:

.

Согласно теореме между вершинами 2 и 3, 1 и 4 и т.д. имеется некоторое число маршрутов длиной 2 (поскольку степень матрицы равна двум). Число маршрутов здесь не используется, важен сам факт наличия маршрута и его длина, на что и указывает ненулевой элемент степени матрицы, не совпадающий с элементом, отмеченным при вычислении маршрута меньшей длины. Проставляем 2 в незаполненные элементы матрицы расстояний и получаем следующее приближение:

.

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