Орграфы. Основные понятия.

Ор.графом наз. пара множеств, элементы 1-го множества наз. вершинами, элементы 2-го множества наз. дугами. Мн-во дуг – некоторое мн-во упорядоченных пар вершин: это озн. , что (i,j) и (j,i) различные дуги.

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

Дуги вида (i,j),(j,i) наз. паралельными. Ор.граф наз. простым, если он не имеет паралельных дуг. Число дуг, входящих в вершину наз. полустепенью захода d- (i).

Число дуг, выходящих из вершины наз. полустепенью исхода d +(i). ,где n-число дуг. При таком сумми-ровании каждая дуга учитывает-ся n раз. Граф D=(N,W) лежит в основе графа G=(N,U), если он имеет то же мн-во вершин и лю-бые две вершины в D смежны тогда и только тогда, когда они смежны в графе D.

Последовательность вершин ор.графа наз. маршрутом, если для любых двух соседних вершин в этой последовательности в ор.графе существует дуга (Ip,Ip+n) принадлежит U. Маршрут замкнут, если первая и последняя вершины совпадают. В противном случае – открытый.Последовательность вершин, где любые две соседние смежные наз. полумаршрутом. Маршрут, у которого все дуги различны наз. путем. Полумаршрут, у которого все дуги различны наз. полупутем. Замкнутый путь наз. контуром. Замкнутый полупуть наз. полу-контуром. Контур (полуконтур) наз. простым, если все вершины в этом контуре за исключением 1-го и последнего различны. (Аналогично для пути и полупути).

Типы связности ор.графа. Ор.граф наз. двусторонне связным, если для любой пары вер-шин(i,j) в ор.графе существует маршрут из i в j и из j в i. Ор. граф наз.односторонне связным, если для любой пары вершин(i,j) существует маршрут, соединяющий эти вершины(хоть 1). Ор. граф наз. слабосвязным,если ле-жащий в его основе граф связен или же, когда для любой пары вершин сущ. Полумаршрут, сое-диняющий эти вершины. Если граф сильно связен,то он слабо-связен и односторонне.Если он односторонне связан, то он и слабосвязен. Граф наз. не связным, если он даже не слабосвязен.

28. Содержание

    • Множества. Основные понятия.
    • Операции над множествами и их свойства.
    • Декартово произведение. Разбиение множеств.
    • Алгебра множеств
    • Отношение. Бинарное отношение
    • Алгебра бинарных отношений
    • Отображение. Виды отображений
    • Отношение порядка. Изоморфизм упорядоченных множеств.
    • Алгебраические системы. Изоморфизм алгебраических систем.
    • Функции алгебры логики.
    • Формулы. Реализация функций формулами.
    • Эквивалентность формул. Свойства элементарных булевых функций.
    • Двойственные функции. Принцип двойственности
    • Разложение булевых функций по переменным. Сднф.
    • Разложение булевых функций по переменным. Скнф.
    • Полнота и замкнутость.
    • Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
    • Классы т0, т1.
    • Класс s.
    • Класс м.
    • Класс l
    • Задача минимизации булевых функций.
    • Задача минимизации булевых функций в геометрической постановке.
    • Сокращенные днф.
    • Тупиковые днф и решение задачи минимизации.
    • Графы. Основные понятия.
    • Орграфы. Основные понятия.
    • Маршруты. Цепи. Циклы. Связность.
    • Операции над графами
    • 30.Двудольные графы.
    • 31. Планарные графы.
    • 32. Эйлеровы и гамильтоновы графы
    • 33. Дерево. Лес
    • 34. Графическое разбиение.
    • 35. Способы задания графов
    • 36. Типы связности орграфов
    • 38. Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.
    • 39. Задача о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона.
    • 40. Теорема Форда-Фалкерсона