22222222222222222222222222222222222222222222
- 2. Определить цикломатическое число σ (G) для данного графа G.
Минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим.
σ (G) = m – n + k; k=1– для связанных графов
Где m – кол-во ребер, n – кол-во вершин, k – Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
Цикломатическое число указывает на: Число независимых циклов в графе.
- 3. Определить хроматическое число γ (G) для данного графа G.
Число красок необходимое для раскрашивания всех вершин графа.
Хроматическое число графа определяется: минимальным числом красок при раскраске вершин.
- 4. Определить число внутренней устойчивости графа α 0(G).
Указывает на максимальное число несмежных (не связанных напрямую ребрами) между собой вершин графа!
Число внутренней устойчивости графа определяет: число вершин в наибольшем пустом подграфе.
- 5. Определить число внешней устойчивости графа β 0(G).
Минимальное число вершин, образами которых являются все остальные вершины графа. Не определяется для графов с изолированными вершинами!
Число внешней устойчивости графа определяет: минимальное число вершин для вершинного покрытия.
- 6. Определить число паросочетаний графа α 1(G).
Максимальное число ребер! несмежных между собой.
Число паросочетаний определяет: наибольшее число попарно несмежных ребер.
- 7. Определить число реберного покрытия графа β 1(G).
Минимально количество ребер для покрытия всех вершин графа.
Число реберного покрытия определяет в графе: минимальное число ребер для вершинного покрытия.
- 8. Определить кликовое число φ (G) для данного графа G.
Максимально количество смежных вершин.
Кликовое число определяет в графе: число вершин в наибольшем полном подграфе (НПП).
- 9. Определить радиус r(G) для данного графа G.
Радиус графа — минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум называется центральной вершиной.
Радиус графа определяется: минимальным эксцентриситетом.
- 10. Определить диаметр d(G) для данного графа G.
Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер, которые необходимо пройти, чтобы добраться из одной вершины в другую.
Диаметр графа определяется: максимальным расстоянием между парой вершин.
- Какое множество вершин является центром графа?
Центр графа включает только те вершины, расстояние от которых до самой дальней вершины минимально.
Центр графа включает только те вершины, у которых: эксцентриситет совпадает с радиусом графа.
3333333333333333333333333333333333333333333333333333333
СП – математическая модель отражающая структуру и динамику дискретных систем и исследуемые свойства моделируемой системы.
Ординарная СП- СП без кратных дуг.
Неординарная СП – СП с кратными дугами.
Автоматная СП – ординарная СП в которой каждый переход имеет только одну входную и одну выходную позицию.
Синхрограф – ординарная СП в которой у каждой позиции ровно одна входная и ровно одна выходная дуга.
Множество достижимости СП – множество всех возможных маркировок, которые могут быть при функционировании данной СП.
Безопасная СП – маркированная СП в процессе функционирования которой, емкости позиций могут принимать значения 0 или 1, иначе сеть называется небезопасной.
K-ограниченная СП – маркированная СП в процессе функционирования которой емкости позиций не превышают некоторого значения k.
Строгосохраняющая СП – маркированная СП в которой суммарное количество фишек не меняется.
Сохраняющая СП – маркированная СП в процессе функционирования котjрой общее количество фишек меняется, но можно найти вектор W (W1, W2, W3, …, Wn).
Живая СП – маркированная СП, в которой для каждого перехода ti при любой маркировке μ, достижимой из μ0, можно получить такую маркировку μ', при которой этот переход будет разрешен.
Наличие тупиковых маркировок означает, что СП неживая.
444444444444444444444444444444444444444444444444444444
Множество состоит из элементов, каждый из которых воспроизводится, как отдельное целое.
Обозначается заглавными буквами лат. алфавита.
Мощность множества определяется его кол-вом его элементов (пустое, бесконечное, конечное).
Равенство А и Б - все элементы А содержатся в Б, все элементы Б содержатся в А.
Включение А в Б - все элементы А содержатся в Б (А - подмножество).
Равенство - частный случай включения.
Булеан - нечёткое множество, представляющее собой множество всех подмножеств.
СИмметрическая разность.
Дополнение до множества.
Декартово произведение - множество упорядоченных пар.
Отображение - закон, устанавливающий соответствие между множествами А и Б.
Однозначное - для каждого оригинала - один образ.
Взаимнооднозначное отображение (биекция) - каждый оригинал имеет один образ, каждый образ - один оригинал.
Многозначное - для каждого оригинала существует образ (не единственный).
Эквивалентность - одновременная симметричность, рефлексивность и транзитивность.
Классом эквивалентности по отношению к отношению эквивалентности наз. множество, порождённое некоторым элементом из множества в отношении R.
Фактор множества - множество классов экв. постр. на исходном множестве Х в отношении R.
Отношение порядка - всякое антирефлксивное, антисимметричное и антитранзитивное отношение (частичного порядка).
Диаграмма Хоссэ - начальные точки и отрезки, изображающие элементы упорядоченного множества, с отрезками, соединёнными таким образом (тот, что покрывает всегда выше в отношении R). Строится снизу вверх.
Доминирование - бинарно, антитранзитивно.
Граф - графическое отображение бинарного, как данного на R как подмножество декартового произведения.
Кол-во вершин и рёбер - характерные размеры графов.
Орграф - антисимметричный граф.
Неограф - состоит из рёбер (без дуг).
Смешанные.
Псевдограф - обобщённое понятие графа, содержащего дуги, рёбра, кратные дуги и рёбра.
Мультиграф - граф без петель (рефлексивных отношений).
Мультичисло - максимальное число рёбер или дуг.
Скелет - граф без кратных рёбер, петель.
Полный граф - все вершины соединены ребром.
Степень (валентность) - числовая характеристика, равная количеству рёбер, инцидентных к данной вершине.
Полустепень захода, полустепень исхода (хар-ки, определяющие кол-во входящих или исходящих дуг соотв.).
Регулярный граф - это скелет, у которого локальные степени всех вершин равны. (частный случай - полный граф)
Взвешенный - граф, вершинам или рёбрам которого приписаны числовые величины, наз. весом или стоимостью.
Смежные вершины принадлежат одному ребру (дуге).
Смежные рёбра имеют хотя бы одну общую вершину.
Смежные дуги имеют общую вершину захода.
Маршрут - упорядоченная последовательность рёбер или вершин, в которой каждые соседние два ребра смежны между собой.
Длина маршрута - количество рёбер.
Цепь - маршрут, в котором не повторяются рёбра.
Простая цепь - не повторяются вершины.
Связный граф - граф, каждые две вершины которого могут быть связаны простой цепью.
Компонент связанности несвязанного графа - такая часть графа, в которой для любой пары вершин можно найти простую цепь, но нет простых цепей между вершинами разных компонентов.
Разделяющее множество связанного графа - мнво рёбер, при удалении которого граф становится несвязным, причём компонент связности R=2.
Мост или перешеек в графе - такое ребро единственное, при удалении которого связный граф становится несвязным.
Ориентированный маршрут - такая упорядоченная последовательность дуг или вершин орграфа, в которой вершина стока предыдущей дуги явл. вершиной истока след. дуги.
Путь - маршрут в орграфе, в котором не повторяются дуги.
Простой путь - не повторяются и вершины.
Ассоциированный псевдограф орграфа - граф с заменёнными дугами на рёбра.
Связный орграф - граф, в котором любая пара вершин может быть соединена простым путём (1 с 2 и 2 с 1).
Односторонний связ. орграф - хотя бы один просто путь.
Достижимость и контрдостижимость.
Конденсирование - замена сильной связи на вершину.
Графический, матричный, синаптический.
Матрица смежности неографа симметрична относительно главной диагонали (0,1)
Матрица связанности (0-n)
Матрица инцидентности (+-1,0)
Изоморфные - тождественные по структуре.
Изоморфные графы моделируют одно и то же бинарное отношение с точностью до отображения вершин.
Суграф, надграф, дополнение.
Цикл - замкнутая цепь с повторяющимся первым и последним элементом.
Простой цикл - без повторения вершин.
Полуконтур орграфа - контур без учёта направления дуг.
Независимые циклы - различаются хотя бы одним ребром.
Цикл Эйлера - цикл в связном графе, проходящий через все рёбра.
Полуэйлеров - без одной дуги
Графы эйлера (все вершины чётной степени).
Цикл Гамильтона - цикл, проходящий через все вершины графа.
Дерево - граф без циклов.
Несвязан граф с компонентами связ. деревьями - лес.
Остовным или каркасным деревом связ. графа наз. такой суграф исходного графа, который получен m-n+1 ребром графа.
Корневое дерево с единственной вершиной с полустепенью исхода равной нулю.
Упорядоченное дерево - сыновья вершины упорядочены и изображены слева направо.
Бинарное дерево (двоичное)- у каждой вершины может быть только два сына.
Полное бинарное дерево - только два сына, либо лист.
Двудольные графы - Кёнига.
Т.Кёнига - все простые циклы чётное длины.
Цикломатическое число - количество независимых циклов в графе (убрать m-n+1 рёбер, чтобы получить дерево).
Хроматическое число - необходимое для раскраски графа число красок.
Граф Кёнига - бихроматический.
Число внутренней устойчивости, независимости, неплотности - макс. количество вершин в графе, не смежных между собой.
Число внешней устойчивости - число вершин, образами которых являются все остальные вершины.
Кликовое - максимальное число вершин, смежных между собой.
Число паросочетания графа - число рёбер в наибольшем паросочетании графа.
Число рёберного покрытия - минимальное число рёбер для покрытия всех вершин.
Расстояние между вершинами - количество рёбер в минимальном маршруте.
Диаметр - максимальное расстояние между вершинами.
Максимальное удаление (эксцентриситет) - максимальное расстояние от данной вершины до любой другой.
Радиус - минимальный эксцентриситет графа.
Центр графа - множество вершин, для которых эксцентриситет равен радиусу графа.
Плоский - может быть изображён без пересечения и самопересечения рёбер.
Планарный - имеющий изоморфный плоский граф.
Грань плоского графа - мах. по включ. точки плоскости, каждую из которых можно соединить жардановой кривой.
Внутренние и внешние. (1 внешняя грань)
Стереограф - проекция плоского графа, позволяющего превратить любую внутреннюю грань во внешнюю.
(Любая точка плоского графа может принадлежать внешней грани)
(Склейка плоских графов по вершинам - плоский граф)
(Если соединить две точки наход. на границе плоской грани жардановой кривой, грань разбивается на 2 плоские грани)
(Точка на ребре, не совпадающая с вершиной, приндлежит двум граням (ребро не мост) и одной (ребро - мост))
(n-m+f=2 f-колво граней плоского nm графа)
(n<=3n-6 в планарном графе колво рёбер не должно превышать правую часть)
Понтригина-Куратовского (критерий планарности графов)
Гомеоморфные графы - могут быть получены операциями расщепления с заменой бинарными рёбрами и стяжкой бинарных рёбер.
ГИПЕРГРАФЫ
Смежные вершины - принадлежат одному ребру.
Смежные рёбра - Пересечение множеств вершин не равно нулю.
Степень вершины - мощность множества рёбер вершины.
Если степени всех вершин гг равны - Nуниформный или Nоднородный.
Веришна инцидентна ребру, если множество вершин ребра содержит данную вершину.
Граф, двойственный к двойственному - исходный.
Цепь в ГГ (все вершины различны, все гиперрёбра различны, вершины справа и слева гиперребра инцидентны)
Две вершины связаны, если можно построить цепь. ГГ связан, если все вершины связаны.
Цепь в Кёниговом представлении длиной 2l+1
Цикломатический ранг - цикломатическое число кёнига.
Сильно связный подграф ориентированного графа называется зоной.
Зона, максимальная относительно включения вершин, называется компонентой сильной связности (бикомпонентой).
Полнота aRb или bRa.
Эквивалент - реф, транз, симм.
Толерантность - рефлексивность, симм
Доминирование - антирефлекс, антисимм
Порядок - рефл, антисимметр, транзит
Строгого порядка - антирефл, антисимметр, транзит
Квазипорядок - рефлексивность, транзитивность
ПРедикации - анти, анти, анти
1. Как называется отношение между множествами А и В, если множество А является подмножеством множества В?
2. Всякое бинарное отношение, обладающее свойствами антирефлексивности, антисимметричности, называется отношением ...
3. Чему равна полустепень захода корневой вершины в корневом дереве?
4. Как называется орграф D*, вершины которого соответствуют сильным компонентам связности исходгого орграфа D, а дуги - связям между вершинами соответствующих компонент связности?
5. Укажите имя ученого, сформулировавшего критерий двудольности графа?
6. Цикл гиперграфа соответствует ... в его Кениговом представлении.
7. Гиперребро - это непустое ... множества вершин гиперграфа.
8. Логическое отношение нескольких условий, при истинном значении которого некоторое событие может реализоваться в дискретной системе, называется ...
9. Определенное сочетание нескольких условий, на которое будет влиять реализация некоторого события в дискретной системе, называется ...
10. Установите соответствие между названием сети Петри (СП) и ее определением.
1. строго сохраняющаяся СП
2. сохраняющаяся СП
3. ограниченная СП
4. живая СП
5. безопасная СП
маркированная СП, в которой в процессе функционирования общее число маркеров остается постоянным.
маркированная СП, для которой существует положительный ненулевой вектор, произведение которого на вектор маркировки в любой момент функционирования остается постоянным.
маркированная СП, в которой число маркеров в любой позиции никогда не превышает 1.
маркированная СП, в которой каждый переход в процессе функционирования будет разрешен при маркировке, полученной из исходной с помощью совокупности отношений непосредственного следования.
маркированная СП, в которой число маркеров в любой позиции никогда не превышает k, где k - некоторое счетное число.
1. Включение
2. строгого порядка
3. 0
4. зона
5. Кёниг
6. циклу
7. подмножество
8.
9. маркировка?
20. 1.1 5.3 3.5 2.2 4.4
_____________________________
1.Разрешённый переход - это.. [4 checkbox] "переход, кол-во меток каждой из входных позиций которого больше или равно кратности дуг, соединяющих данную позицию с переходом"
2.Назовите бинарное отношение, при котором aPb и bPa. [textarea] "симметричность"
3.#(Pk,I(Ti)) - это.. [4 checkbox]. "кратность входной позиции"
4.Понятие аналогичное маршруту в орграфе. [textarea] "путь"
5.Характеристика, показывающая число элементов множества. [textarea] "мощность"
6.Модель для отображения n-арных отношений. [textarea] "гиперграф"
7.[textarea] "входная" [позиция]
8.Могут ли повторяться рёбра в цепи гиперграфа (да/нет). [textarea] "нет"
9.Кол-во рёбер в дереве с n вершинами. [textarea] "n-1"
10.Кол-во цветов, необходимое для раскраски двудольного графа. [textarea] "2"
5555555555555555555555555555555555555555555555555555555555
1. Как называется отношение между множествами А и В, если множество А является подмножеством множества В? включение
2. Всякое бинарное отношение, обладающее свойствами антирефлексивности, антисимметричности, называется отношением ... строгого порядка
3. Чему равна полустепень захода корневой вершины в корневом дереве? 0
4. Как называется орграф D*, вершины которого соответствуют сильным компонентам связности исходгого орграфа D, а дуги - связям между вершинами соответствующих компонент связности? зона
5. Укажите имя ученого, сформулировавшего критерий двудольности графа? Кёниг
6. Цикл гиперграфа соответствует ... в его Кениговом представлении. циклу
7. Гиперребро - это непустое ... множества вершин гиперграфа. подмножество
8. Логическое отношение нескольких условий, при истинном значении которого некоторое событие может реализоваться в дискретной системе, называется ...
9. Определенное сочетание нескольких условий, на которое будет влиять реализация некоторого события в дискретной системе, называется ...
10. Установите соответствие между названием сети Петри (СП) и ее определением.
1. строго сохраняющаяся СП маркированная СП, в которой в процессе функционирования общее число маркеров остается постоянным.
2. сохраняющаяся СП маркированная СП, для которой существует положительный ненулевой вектор, произведение которого на вектор маркировки в любой момент функционирования остается постоянным.
3. ограниченная СП маркированная СП, в которой число маркеров в любой позиции никогда не превышает k, где k - некоторое счетное число.
4. живая СП маркированная СП, в которой каждый переход в процессе функционирования будет разрешен при маркировке, полученной из исходной с помощью совокупности отношений непосредственного следования.
5. безопасная СП маркированная СП, в которой число маркеров в любой позиции никогда не превышает 1.
1.Разрешённый переход - это.. [4 checkbox] "переход, кол-во меток каждой из входных позиций которого больше или равно кратности дуг, соединяющих данную позицию с переходом"
2.Назовите бинарное отношение, при котором aPb и bPa. [textarea] "симметричность"
3.#(Pk,I(Ti)) - это.. [4 checkbox]. "кратность входной позиции"
4.Понятие аналогичное маршруту в орграфе. [textarea] "путь"
5.Характеристика, показывающая число элементов множества. [textarea] "мощность"
6.Модель для отображения n-арных отношений. [textarea] "гиперграф"
7.[textarea] "входная" [позиция]
8.Могут ли повторяться рёбра в цепи гиперграфа (да/нет). [textarea] "нет"
9.Кол-во рёбер в дереве с n вершинами. [textarea] "n-1"
10.Кол-во цветов, необходимое для раскраски двудольного графа. [textarea] "2"
0000000000000000000000000000000000000000000000000000000000000
Цепь – маршрут без повтора ребер
Простая цепь – цепь без повтора вершин.
Связный – граф, между любой парой вершин которого существует как минимум один путь.
Псевдограф – граф, в котором допускаются кратные ребра и дуги, а так же петли.
Дерево – связный граф без циклов
Мультиграф – псевдограф в котором есть кратные дуги, ребра, но отсутствуют пелти.
Граф Эйлера – связный граф, содержащий циклы Эйлера. (Цикл эйлера – замкнутая простая цепь, проходящая через все ребра). Степени всех вершин четные!!!
Регулярный – обыкновенный граф, степени вершин в котором равны между собой.
Пустой – граф без ребер.
Насыщенный – граф, добавление одного ребра в который приводит к возникновению полного графа.
Лес – несвязный граф без циклов.
Полный – обыкновенный неограф, в котором каждая пара вершин соединена ребром.
Граф Гамильтона – граф, содержащий хотя бы один цикл Гамильтона (Цикл Гамильтона – замкнутая цепь, проходящая через все вершины связного графа)
Граф Гамильтона, если для любое его вершины локальная степень >= n/2.
Локальная степень вершины — число рёбер ей инцидентных. Петля дает вклад, равный «2» в степень вершины.
Скелет(остовное дерево) - ациклический связный подграф данного графа, в который входят все его вершины.