В случае ОГ: -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.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.