28.Понятие граф орграф.

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

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

Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) — гиперссылки (см. Тематическая карта).

Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами

29.Понятие смежности, инцидентности,степени.

Определение. Если е = {v, w} – ребро графа, то вершины v, w называются концами ребра е; в этом случае также говорят, что ребро е соединяет вершины v, w.

Определение. Если е = {v, w} – дуга орграфа, то вершина v называется началом, а вершина w – концом дуги е; в этом случае также говорят, что дуга е исходит из вершины v и заходит в вершину w.

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v, w, если оно соединяет эти вершины и наоборот, каждая из вершин v, w инцидентна ребру е.

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

Определение.Степенью вершины v графа G называется число d(v) ребер графа, которым инцидентна эта вершина.

Определение. Вершина, локальная степень которой равна 0, называется изолированной; степень которой равна 1 – висячей.

Замечание. В случае неориентированного псевдографа  обычно считается, что  вклад каждой петли, инцидентной некоторой вершине v, равен 2 (тогда как вклад любого другого ребра, инцидентного вершине v, равен 1).

Определение.Полустепенью исхода (захода) вершины v орграфа D называется число d⁺(v) (d ^-(v)) дуг орграфа D, исходящих из вершины v (заходящих в вершину v).

Замечание. В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в d⁺(v), так и в d ^-(v).

Количество вершин  и ребер в графе G обозначим соответственно через n(G)  и m(G), а количество вершин и дуг в орграфе D – через n(D) и  m(D).

30.Изоморфиз, гомеорфизм

Изоморфи́зм (от др.-греч. ἴσος — «равный, одинаковый, подобный» и μορφή — «форма») — это очень общее понятие, которое употребляется в различных разделах математики. В общих чертах его можно описать так: пусть даны два множества с определённой структурой (группы, кольца, линейные пространства и т. п.). Биекция между ними называется изоморфизмом, если она сохраняет эту структуру. Если между такими множествами существует изоморфизм, то они называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких множеств со структурой.

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

Изоморфизм графов

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

В теории вычислительной сложности до сих пор является открытым вопрос о сложности задачи изоморфности графов. На данный момент не доказана ни её принадлежность классу  , ни её  -полнота.

Гомеорфизм- это взаимно-однозначное и непрерывное отображение. Пространства, связанные гомеоморфизмом, топологически неразличимы.

Пусть   и   — два топологических пространства. Функция   называется гомеоморфизмом, если она взаимно однозначна, а также   и   непрерывны.

Пространства   и   в таком случае называются гомеомо́рфными или топологи́чески эквивале́нтными.