|
|
Множествами объединение, пересечение, разность и симметрическая разность, дополнение. Свойства операций и принцип двойственности правила
              
Маршруты. Цепи. Циклы. Связность графа.
Нахождение простых цепей.
Ответ:
Маршрутом длины n называется непустая последовательность n ребер вида v1, e1, v2, e2, v3,e3 , …, vn, en, vn+1 , где ребро ��
(j = 1, 2, …, n) соединяет вершины vj и vj+1.
Маршрут, в котором все
рёбра попарно различны, называется цепью.
Замкнутый маршрут, являющийся цепью, называется циклом.
Граф называется связным, если любая пара его вершин связана.
|
Пример применения метода нахождения всех простых цепей для контактных схем.
Ответ:
Этот метод может быть использован в следующих задачах:
Задача Коммивояжера.
Составление маршрутов путешествий, поездов, транспорта.
В электрических схемах.
При анализе контактных цепей
|
Эйлеровы цепи и циклы. Уникурсальная линия. Важные теоремы.
Ответ:
Эйлерова цепь — это путь, проходящий по всем рёбрам графа и притом только по одному разу. Эйлеров цикл — эйлерова цепь, являющийся циклом. То есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
Уникурсальная линия – всякая линия, которую можно провести, проходя по заданным участкам точно по одному разу. Теорема 1: Если в связном графе все вершины четны, то этот граф содержит эйлеров цикл.
Теорема 2: Если в связном графе две вершины нечетны, а все остальные – четны, то этот граф содержит эйлерову разомкнутую цепь.
Теорема 3: Если в связном графе G содержит 2k нечетных вершин, то в нем имеется k разомкнутых эйлеровых цепей, в совокупности содержащих все ребра графа G точно по одному разу.
Теорема 4: В любом связном графе можно построить замкнутый маршрут, проходящий через каждое ребро точно два раза.
|
Двудольные графы. Граф G3,3.
Если любая вершина, принадлежащая подмножеству V1 соединена с вершиной подмножества V2, то такой граф называется двудольным.
Двудольный граф – полный, если каждая вершина из 1-й доли соединена с каждой вершиной 2-й доли. Число ребер в нем K=|V1|∙|V2|
Этот граф не может быть плоским. В n-дольном графе V1, V2, … Vn, т.е. V = V1 ∪ V2 ∪ … ∪ Vn
Vi,j Vi ⋂Vj= ∅, i≠j
Дополнение полного двудольного графа есть несвязный граф, состоящий из 2 компонентов, которые являются полными связными графами
� = �1(�1 − 1) = �2
1 2 �1
� = �2(�2 − 1) = �2
2 2 �2
|
Вводные понятия. Теорема Эйлера о плоских графах. Ответ:
Плоским называется граф, изображенный на плоскости так, что его ребра пересекаются только в вершинах.
Граф называется планарным, если у него есть плоское изображение. Грань – часть плоскости, ограниченная со всех сторон ребрами и не содержащая внутри себя ни вершин, ни ребер.
Теорема Эйлера о плоских графах : Пусть n – число вершин связного плоского графа G, r – число ребер и q
– число граней. Тогда n+q=r+2.
|
Гомеоморфизм. Теорема «о не планарности двудольных графов
��, ��,�». Критерий планарности Понтрягина-Куратовского.
Ответ:
Гомеоморфными фигурами для которых мы будем ставить в соответствие такие фигуры которые получаются друг от друга методом неразрушающей деформации.
Два графа называются гомеоморфными если существуют их подразбиения являющееся изоморфными.
(Возьмем 2 вершины которые соединены ребром, заменим ребро вершиной на ребе т.е. увеличим число вершин на1 и число ребер на 1 – подразбиение ребра(увеличение-подразбиение) (уменьшение –надразбиение)
Вывод: Гомеоморфные графы к изоморфным графом.
Критерий Понтрягина-Куратовского Замечание: Преобразование некоторого графа к плоскому если оно возможно находит применение в монтаже схем, чтоб не возникало не нужных, не продуманных эл.соеденений.
Зам: Планарным является любой двудольный граф с числом вершин n=1,2,3,4,5,6 за исключением полного двудольного графа типа G33 т.е. граф G33 не имеет плоского представления.
Зам: Любой граф с числом вершин n=1,2,3,4,5 является планарным кроме полного графа с 5 вершинами обозначается G5 т.е G5 не имеет плоского представления. Критерий: Граф планарный если он не содержит подграфов, гомеоморфный графам g5 и G3 Для проверки на планарность необходимо перебрать C в 5
+С в 6 подграфов.
|
Двойственные графы. Инверсные структуры и двойственные графы.
Ответ:
Двойственным графом по отношению к связному графу G является граф G’ построенный следующим образом:
а) В каждой грани исходного графа G ставится новая вершина G’
б) Если какая либо вершина графа G’ отделена ребром исходного графа G от другой вершины двойственного графа G’ тогда эти вершины двойственного графа G соединяются ребром. Инверсные структуры и двойственные графы: Рассмотрим двухполюсник реализующий Б.Ф. зависящий от семи переменных построим для нее инверсную структуру. Представим для этого двухполюсник в виде плоского графа, для которого будет построен двойственный граф соответствующий инверсной схеме и затем восстановлена сама инверсная структура в виде двухполюсника.
Замечание: Алгоритм построения двойственного графа адаптирован к законам электроники т.е. во внешней грани исходного графа будем ставить не 1 новую вершину, а 2 предварительно разбив всю плоскость на 2 полуплоскости в которых соединение новых вершин будет возводится автономно(независимо). При построении инверсной структуры по двойственному графу переменные берутся в инверсном виде для тех ребер двойственного графа которые пересекают в исходном графе(в двухполюснике) ребро с определенным обозначением переменной. Эта переменная в инверсном виде указывается на инверсной схеме.
|
Деревья и лес. Теорема о деревьях и лесе. Остовы графа. Цикломатическое число. Фундаментальная система циклов.
Лес состоит из деревьев связанных графов не содержащих циклов
Теорема о деревьях:
Любое дерево содержит n-1 ребер (n-число вершин)
Любой лес содержит n-k ребер (k-число деревьев(компонентная связь))
Любые 2 вершины дерева соединены точно 1 простой цепью
Если в дереве любые 2 вершины соединить ребром то в графе появится цикл и перестает быть деревом. Если в связном графе содержится цикл то после удаления любого ребра входящего в цикл этот цикл разрушается проделав такую операцию со всеми циклами получим дерево которое наз-ся «остовом» графа.
Определение :
Связный граф данного связного графа G содержащий все вершины G но не содержащий циклы наз-ся остовом исходного графа G. Определение: наименьшее число показывающее сколько ребер необходимо удалить с графа чтобы получить его остов наз-ся цикломатическим числом графа � = � − � +
� = � − � + � Фундаментальная система циклов: обозначим через мн-во М - мн-во удаляемых ребер графа разрушающих все цифры графа. Определение: ФСЦ обозначим Q будем называть все то мн-во циклов которые разрушаются удаляемыми ребрами входящими во множество М. |Q|=z
| |
|
|
Скачать 134.15 Kb.