Краткие ответы на экзаменационные вопросы по дисциплине "Дискретная математика" (Предмет дискретной математики. Метод Блейка-Порецкого), страница 7

В случае ОГ: -1 – вершина явл-ся началом ребра, 1-конец ребра, 0-вершина и ребро не инцидентны, если некоторая вершина яв-ся для ребра и началом и концом (петля), представ-ся любое др. число, например 2.

Списком ребер графа предст. 2 столбцами: в левом – ребро, правом-инцидентные ему вершины. Для НГ – порядок вершин в строке произволен, для ОГ – первым стоит номер начала строки.

Матрицей смежности ||ki|| квадратной матрицей размер n*x gпо ерт и гориз перечисл все вершины VjÎV, а на пересечении к-й и i-й вершин в случае НГ простав-ся, равное числу ребер, соедин-х эти вершины, для ОГ -||ki||=числу ребер с началом в к-й вершине м концом в i-й

Список ребер – сокращенное прдеставление МИ.

Построение МИ по списку ребер. Каждая строка соотв-т строке матрицы с тем же №. Для НГ в строке списка указ. № эл-в строки МИ равны I. Для ОГ в этой строке 1 стоит № эл-та строки матрицы, =-1, а в 2 - № эл-та, равного 1.

Построение по МС списка ребер. Эл-ту МС соот-т ki строк списка ребер,  в каждом из к-х записаны № i,j. Для НГ эти строки соот-т только эл-м верхнего правого треуг-ка МС, т.е. э-мki Сj>=I и для ОГ рассматр-ся все эл-ты ki


39. Эйлеровы и Гамильтоновы гр, плоские гр.

Эйлеров (Э) цикл – цикл графа, содержащий все ребра графа.

Э граф – граф, имеющий эйлеров цикл (ЭЦ можно считать следом пера, вычертившего этот граф, не отрываясь от бумаги.)

Для того, чтобы связный граф без петель был Э, необходимо и достаточно, чтобы степень его вершины была четным числом.

Э-цепь – цепь, включ-я все ребра данного конечного НГ G, но имею щая разные начала V’ и конец V”. Чтобы в конечном НГ G сущ-ла ЭЦ необходимо и достаточно его связанность и четность степеней всех вершин, кроме начальной и конечной (нечетные). Чтобы в конечном ОГ сущ-л ЭЦ необходимо и достаточно его связанность и равенство степеней вершин этого графа по вход. и выход. ребрам.

Гамильтонов (Г) цикл – простой цикл, проходящий через все вершины по одному разу рассматриваемого графа.

Г-цепь – простая цепь, проходящая через все вершины графа по одному разу, с началом и концом в разных вершинах.

Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

Граф, изображенный на плоскости в таком виде, что его ребра пересекаются только в его вершинах, называется плоским.

Теорема Э.

если в плоском графе имеется «г» граней, «в» вершин и «р» ребер, то обязательно выполняется равенство: «г» + «в» - «р»=2.

40. Деревья, бинарные деревья, лес

НГ наз-ся неор. деревом, если он связан и не содержит циклов, а значит петель и кратных ребер.

Дерево – миним-й связный граф в том смысле, что при удалении хотя бы 1 ребра он теряет связанность. В дереве с n вершинами всегда n-1 ребер.

Лес – несвязанный НГ без циклов. Связанные компоненты леса явл-ся деревьями.Если любые 2 вершины связаны единственной цепью, то граф яв. деревом. Вершина V графа G наз-ся концевой (висячей), если ее степень =1. Ребро, инцидентное концевой вершине наз-ся концевым.

Ориентация неор-го дерева осущ-ся след-м образом: в дереве G отмеч-ся вершина V0 – корень дерева G и все ребра такого дерева с корнем, ориентир-ся от этой вершины-корня. Вершину V’ ребра (V’,V”) можно соединить единственной цепью L с корнем V0 .Если эта цепь не содержит ребра (V’,V”), то в это ребро вводицца  ориентация от V’ и V”, в противном случае от V” и V’. Такая ориентация согласована с ориентацией того же рабра, опр-й через вершину V”. Данная ориентация дерева с корнем V0 единственна. Это ориентированное дерево. В нем все ребра имеют направления от корня. При выборе др.вершины – корня – получаем другое ОД.

Пусть V – вершина дерева G с корнем V0; B(V) – мн-во всех вершин, связанных с корнем цепями, проходящими через вершину V. Это мн-во порождат НГ G(V), называемый ветвью вершины Vв дереве с корнем  V0. Если дерево имеет более 2 вершин, то среди них есть неконцевые вершины.

Пусть дано конечное дерево G. Вершинами типа 1 называются его концевые вершины. Если из дерева G удалить все вершины типа 1 и инцидентные им концевые ребра, то в оставшемся дереве G концевые вершины наз-ся вершинами типа 2 в дереве G.