КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Какое бинарное отношение на множествах А, В называется отображением А в В
Важным классом бинарных отношений (не обязательно однородных) являются
отображения. Бинарное отношение f включенное в Ax B называется отображением множества A во множество B , если:
1) для любого a принадлежащего A существует b принадлежащее B : (a,b)
принадлежит f
2) (a ,b)принадлежит f , (a ,b1)принадлежит f следовательно b1= b2 .
Для отображений вместо (a,b )принадлежащее f обычно пишут f( a)= b . Среди отображений выделяют инъективные, сюръективные, биективные
11.Какие способы задания однородного бинарного отношения вы знаете?
а).Перечисление всех его элементов: Пусть А={a,b,c}.Однородное отношение a={(a,a),(b,b),(c,c)} можно назвать отношение совпадения.Действительно,(x,y)принадлежат а тогда и только тогда,когда элементы x,y совпадают.
б)Предикатный: Пусть beta={(x,y)принадлежат RxR|x<=y}.Однородное бинарное отношение beta называется отношением ”меньше или равно”.Вместо записи (5,6)принадлежит betaобычно употребляется другая запись 5<=6.
//Думаю матрицу и графики можно не расписывать//
в).Матричный
г).Графический
д)Могут задаваться формулами x+y < 5 задает бинарное отношение на множестве действительных чисел (под вопросом этот пункт)
e)Графовый
12.Что такое ориентированный граф?
Графом называется совокупность,состоящая из произвольного множества точек и множества линий соединяющих некоторые из этих точек.Точки называются вершинами графа,линии называются ребрами.Могут встречаться ребра с концами в одной и той же вершине-они называются петлями.Если на каждом ребре указана ориентация,то такие ребра называются дугами,а граф-ориентированным графом(орграфом).
Или
Ориентированнымграфом (орграфом) называется пара множеств
G € (A,V) ,
где A – произвольное непустое множество (его элементы называются вершинами графа), V € AxA – множество рёбер. В орграфе рёбра называются также дугами. Фактически V – некоторое бинарное отношение на множестве вершин, оно называется отношением смежности
13.Что такое неориентированный граф?
Неориентированным графом (неорграфом) называется пара множеств
G €( A,V) ,
где A ≠(пустому множеству) (множество вершин), V =( { ai ,aj } | ai ,a j)€ A – некоторое множество неупорядоченных пар вершин (множество рёбер). Как и в случае ориентированного графа,
если в графе имеется ребро { ai ,a j } , то вершины ai , a j называются
смежными. Для неорграфа таким образом определённое бинарное
отношение смежностиявляется,
очевидно, симметричным.
14.Что такое отношение смежности?
Графы удобно задавать с помощью так называемого отношения смежности.Две вершины неориентированного графа без кратных ребер называются смежными,если они соединены ребром.Получаем бинарное отношение,определенное на множестве вершин.Отношение смежности,а значит и граф,можно задать матрицей смежности.
15.Что такое отношение инцидентности?
Еще один способ задания графов-с помощью отношения инцидентности.Вершина графа называется инцидентной ребру,если она является одним из концов этого ребра.Можно говорить также,что ребро инцидентно каждому из своих концов.Если Х-множество вершин,а V-множество ребер графа,то отношение инцидентности beta={(xi,yi)|xi принадлежит X;yi принадлежит Y;xi инцидентно yi}.
16.Что такое отношение достижимости?
Это отношение эквивалентности на множестве вершин неориентированного графа.
На множестве вершин графа можно определить бинарное отношение
достижимости – это множество ( ai ,a j ) таких пар, что существует маршрут с началом ai иконцом a j . Это отношение является отношением эквивалентности. Действительно,
симметричность и транзитивность очевидны. Рефлексивностью отношение достижимости также обладает, так как из a в a всегда есть маршрут – пустой, рёбер в нём нет, длина равна нулю.
17.Что такое отношение взаимной достижимости?
Вершины x и y называются взаимно достижимыми,если существует путь из x в y, а также путь из y в x.
18.Что такое компонента связности? Какой граф называется связным?
Достижимость разбивает все вершины графа на классы эквивалентности вершин.Эти классы называются компонентами связности графа.Если граф имеет всего одну компоненту,то он называется связным.Т.е. связным можно назвать граф,любые вершины которого можно соединить цепью.
19.Что такое сильная компонента связности? Какой граф называется сильно связным?
Множество всех вершин графа разбивается на классы взаимно достижимых вершин.Эти классы называются сильными компонентами связности.Если такая компонента одна,то граф называется сильно связным.
Или(орграф сильно связный если любые две его вершины сильно связаны т.е Две вершины x1 ,x2 сильно связаны , если существует путь из x1 в x2 и из x2 в x1 .Компонента сильной связности орграфа – это его максимальное по включению сильно связные подграфы)
Пример
Три компонента сильной связности (обведены)
20.Какие два графа называются изоморфными?
Два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называютсяизоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин).
21.Что такое дерево? Как связаны число вершин и число рёбер дерева?
Связный неориентированный граф без циклов называется деревом. Деревья – наиболее простой вид графов, в то же время они служат хорошими моделями для различных приложений.
Рассмотрим простейшие свойства деревьев.
Теорема 1. Если дерево имеет n вершин, то у него n 1 ребро.
Доказательство. Применим индукцию по числу вершин n. Для n -1 утверждение очевидно. При n -1 в дереве есть концевая вершина. Действительно, рассмотрим произвольный маршрут: {a0 ,a1 },{a1 ,a2 }, ,{ak-1 ,ak } . Так как циклов нет, то все вершины в нём разные. Если вершина k a не является концевой, то маршрут можно продолжить. Продолжая маршрут, мы обязательно найдём концевую вершину. Теперь удалим концевую вершину вместе с инцидентным ей ребром. Полученный граф – дерево с n -1 вершиной. По предположению индукции оно имеет n-2 ребра. Значит, исходное дерево имеет n-1 ребро. Теорема доказана. Справедливо и утверждение, в некотором смысле обратное.
Теорема 2. Если связный граф имеет n вершин и n-1 ребро, то это дерево. Доказательство. Допустим, в таком графе есть цикл. Удалим любое его ребро, при этом связность графа, очевидно, не нарушится. Будем удалять рёбра, пока в графе есть циклы. В результате получим дерево, в котором n вершин и меньше, чем n -1 ребро. По теореме 1, это невозможно.
Теорема 3. При добавлении к дереву одного ребра в графе появляется один цикл. При удалении из дерева одного ребра получается граф с двумя компонентами связности. Доказательство очень просто. Для каждого связного графа можно определить каркас (стягивающее, или остовное дерево) – дерево, полученное из графа удалением рёбер.
22. Что такое каркас (остовное дерево) графа? Что такое минимальный каркас?
каркас (стягивающее, или остовное дерево) – дерево, полученное из графа удалением рёбер
Большое значение имеет построение минимального каркасадля взвешенных связных графов. Минимальным называется каркас с наименьшей суммой весов рёбер.
23. Для чего нужен и как работает алгоритм Краскала?
Опишем алгоритм Краскала, позволяющий строить минимальный каркас. Пусть дан связный взвешенный граф с n вершинами.
Шаг 1: выберем ребро с наименьшим весом.
Шаг 2: среди оставшихся рёбер выберем ребро с наименьшим весом.
Шаг 3: среди оставшихся рёбер выберем ребро с наименьшим весом, не образующее цикла с рёбрами, выбранными ранее. Шаг 3 повторяется до тех пор, пока не будет выбрано n- 1 ребро. Выбранные n- 1 ребро образуют минимальный каркас.
Обоснование алгоритма. Необходимо убедиться, что шаг 3 возможен, пока не выбрано n-1 ребро. Рассмотрим произвольный момент в работе алгоритма. Допустим, уже выбранные рёбра вместе с инцидентными им вершинами образуют несвязный граф. Тогда добавление ребра, соединяющего компоненты связности (такое существует, ведь исходный граф связен), не приведёт к образованию цикла. Если уже выбранные рёбра образуют связный граф, то обязательно есть свободная вершина – так как если заняты все вершины, то, по теореме 1, выбрано уже n-1 ребро. Добавление ребра, инцидентного свободной вершине, конечно, не приведёт к образованию цикла. Итак, шаг 3 всегда возможен. Если выбрано n -1 ребро, то они обязательно образуют связный граф – иначе, добавляя рёбра, мы получим дерево с n вершинами и большим, чем n -1 числом рёбер.
24Граф G планарен если хотя бы одна из его геометрических интерпретаций такова ,что ребра графа пересекаются только в его вершинах
планарен потому что его можно изобразить так
Планарный граф уже изображенный на плоскости в таком виде ,что его ребра пересекаются только в вершинах называется плоским.
Неплоский граф – полный граф с пятью вершинами который нельзя уложить на плоскости
Пример 
Сформулируйте критерий планарности графа (теорема Понтрягина-Куратовского).
Теорема 5 (теорема Понтрягина–Куратовского). Граф является плоским тогда и только тогда, когда в нём нет подграфа, который можно «сжать» до одного из графов, V5 и K3,3
V5- полный граф с пятью вершинами
K3,3 – двудольный граф с тремя вершинами
Сжатие графа – это удаление вершины степени 2 и замена двух инцидентных ей рёбер одним ребром
Конечно, это действие может быть повторено несколько раз. Напомним также, что подграфом называется граф, полученный удалением некоторых вершин и (или) рёбер.
Дата добавления: 2015-01-19; просмотров: 114; Мы поможем в написании вашей работы!; Нарушение авторских прав |