Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Задание 8




Отношение f является функцией, т.к. каждому значению x соответствует единственное значение y.

Отношение f не является инъективным, т.к. значению y соответствуют два значения x. Например, y=5, x1=0, x2= -3.

Отношение f не является сюръективным, т.к. не существует x для отрицательных значений y.

Отношение является отображением, т.к. можно рассчитать y для всех x из множества R.


Теория графов

 

Основные понятия и определения

· Граф – пара множеств V и X - G = (V,X). V – множество вершин, X – множество ребер.

· Петля – ребро вида (v,v).

· Кратные рёбра – одинаковые пары в X.

· Ориентированный граф (орграф D) – граф, для которого пары в Х упорядочены. Ребра в орграфе называются дугами и обозначаются <u,v>.

· Степенью вершины V графа G называется число d(v) рёбер графа, инцидентных вершине v. Если d(v) = 1, тогда v – висячая вершина, если d(v) = 0, тогда v –изолированная вершина.

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

· Маршрутом для графа G (путём для орграфа D) называется последовательность v1x1v2x2v3. . .xkvk+1.

· Цепь – незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

· Простая цепь – цепь, в которой все вершины попарно различны.

· Цикл (контур) - замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

· Простой цикл (контур) - цикл (контур), в котором все вершины попарно различны.

· Длина пути – число рёбер (дуг) в маршруте (пути).

· Путь в графе называется минимальным, если он состоит из минимального количества рёбер.

· Орграф D называется нагруженным, если на множестве дуг Х определена весовая функция – длина дуги хÎХ.

· Путь называется минимальным в нагруженном графе или орграфе, если он имеет минимальную длину пути.

· Матрица смежности (графа, орграфа): А = [aij], V = {v1…,vn},

· X = {x1…,xm}

·


· Матрица инцидентности: B = [bij]

· (орграфа D)

·

 

· (графа G)

·

 

· Матрица достижимости T = [tij]

·

 

· Матрица связности S = [sij]

· (орграфа D)

 

· (графа G)

 

· Дерево –связный граф без циклов

· Остовное дерево графа (ОД) – любой связный подграф связного графа, содержащий все вершины и являющийся деревом.

Минимальное остовное дерево (МОД) – остовное дерево нагруженного графа с минимальной суммой длин дуг, содержащихся в нём.

 

· Цикломатическое число связного графа G (число циклов в базисе циклов графа) , где n – количество вершин, m – количество ребер в графе.





mylektsii.ru - Мои Лекции - 2015-2018 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал