Формула Эйлера для числа вершин, ребер и граней плоского графа

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

Итак, формула Эйлера:

где n – число вершин, m – число ребер графа, f – число граней графа.

Исходя из этой формулы, был сформулирован ряд следствий:

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

Следствие 2. Каждый планарный граф G с n ≥ 4 вершинами имеет, по крайней мере, четыре вершины со степенями, не превышающими 5.

Следствие 3. Если G – связный простой планарный граф с n ≥ 3 вершинами и m ребрами, то m ≤ 3n – 6.

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

ПРИЛОЖЕНИЕ 3

Непрерывные одномерные распределения вероятностей

Нормальное распределение (Гаусса)

Непрерывная случайная величина x распределена нормально с математическим ожиданием (центром) μ и дисперсией σ², если

Здесь F(X) – функция распределения (рис. 1), а w(X) – плотность распределения (рис. 2).

Рис. 1. Вид функции нормального распределения вероятностей F(X)

Рис. 2. Вид плотности нормального распределения вероятностей w(X)

Равномерное (прямоугольное) распределение

Функция распределения на интервале (μ-a, μ+a) равна:

и имеет вид, показанный на рис. 3.

Рис.3. Вид функции равномерного распределения вероятностей F(X)

Плотность равномерного распределения на интервале (μ-a, μ+a) равна:

и имеет вид, показанный на рис. 4.

Рис.4. Вид плотности равномерного распределения вероятностей w(X)

Дисперсия для равномерного распределения имеет значение:

D(X)=a²/3.

Распределение Лапласа

Функция распределения равна:

и имеет вид, показанный на рис.5.

Рис.5. Вид функции распределения Лапласа для μ=0,5 и β=0,1

Плотность распределения Лапласа равна:

и имеет вид, показанный на рис.6.

Рис.6. Вид плотности распределения Лапласа для μ=0,5 и β=0,1

Значение дисперсии составляет: D(X)=2β².

Вырожденное (причинное) распределение

Функция распределения равна единичной ступенчатой функции (рис.7):

Рис.7. Вид функции вырожденного распределения F(X)

Плотность распределения равна дельта-функции Дирака:

и имеет вид, показанный на рис.8.

Рис.8. Вид плотности вырожденного распределения w(X)

Приложение 4 Краткие сведения о специализированных языках и проблемно-ориентированных системах имитационного моделирования

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

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

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

Наибольшее распространение в этом классе получил язык GASP, который может быть реализован на любой вычислительной системе, имеющей в программной среде компилятор с FORTRAN-IV. Существенным недостатком класса является отсутствие концептуальной выразительности и средств для проверки логики имитационной модели;

2 – ориентация на системы дифференциальных уравнений, удобная для реализации группы исследовательских моделей, породила класс языков, ярким представителем которого является DYNAMO и распространенный в России его диалект ИМИТАК.

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

Оставшиеся языки многие исследователи делят на две школы: школу фирмы IBM, где применяется язык GPSS, использующий в качестве дескрипторов схемные символы, и школу, использующую операторные языки;

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

Примером такого языка может служить SIMSCRIPT, пока не нашедший широкого применения в исследовательской практике;

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

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

По причине значительной трудоемкости имитационное моделирование применялось только как метод исследований в научной деятельности и крайне редко – в практической работе. Однако, задачи практики требовали создания языков моделирования, более применимых в работе по управлению объектами более широкого класса, нежели уникальные научные установки. И к середине 80-х годов было создано в основном американскими фирмами, по данным Емельянова А.А., более 20 различных систем. К числу них относились уже упомянутые выше GASP, SIMULA, GPSS и SLAM.

Process Charter-1.0.2

Process Charter-1.0.2 (Процесс Чартер), разработчик – компания Scitor, Калифорния, США.

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

Powersim-2.01

Powersim-2.01 (Пауерсим), разработчик компания Modell Data, Берген, Норвегия.

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

Lthink-3.0.61

Lthink-3.0.61 (Лтинк), разработчик компания High Performans Systems, Ганновер, Германия.

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

Extend+BPR-3.1

Extend+BPR-3.1 (Экстенд+БПР), разработчик – Imagine That!, Сан-Хосе, США.

Пакет, Экстенд+БПР, специально предназначен для анализа бизнес-проектов и также поддерживает дискретное и непрерывное моделирование. К числу достоинств нужно отнести понятную среду построения моделей с помощью блоков, множество встроенных блоков и функций для облегчения конструирования моделей, средства построения дополнительных функций посредством встроенного языка. К сожалению, данный пакет используется в достаточном объеме только на компьютерах Макинтош и имеет высокую стоимость порядка 1200 долларов.

ReThink

ReThink (Ретинк), разработчик – Gensym, Кембридж, Массачусетс, США.

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

Piligrim-2.1

Piligrim-2.1 (Пилигрим) совместной разработки МегаТрон, Москва, Keisy, Гаага, Нидерланды и Энит, Таллин, Эстония.

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

Arena-BE 3.6.1

Arena-BE 3.6.1, разработчик – Systems Modeling (Rockwell Software),

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

Имитационная модель компании Systems Modeling включает следующие основные элементы: источники и стоки (Create и Dispose), процессы (Process) и очереди (Queue). Источники – это элементы, от которых в модель поступает информация или объекты. Скорость поступления данных или объектов от источника обычно задается статистической функцией. Сток – это устройство для приема информации или объектов. Понятие очереди близко к понятию хранилища данных – это место, где объекты ожидают обработки. Времена обработки объектов (производительность) в разных процессах могут быть разными. В результате перед некоторыми процессами могут накапливаться объекты, ожидающие своей очереди. Часто целью имитационного моделирования является минимизация количества объектов в очередях. Тип очереди в имитационной модели может быть конкретизирован. Очередь может быть похожа на стек: пришедшие последними в очередь объекты первыми отправляются на дальнейшую обработку (LIFO: last-in-first-out). Альтернативой стеку может быть последовательная обработка, когда первыми на дальнейшую обработку отправляются объекты, пришедшие первыми (FIFO: first-in-first-out). Могут быть заданы и более сложные алгоритмы обработки очереди. Процессы – это аналог работ в функциональной модели. В имитационной модели может быть задана производительность процессов.