ребро, граф, вершина, дуга, петля и цикл что это такое в информатике? каждое объяснение каждого слова.
Граф — совокупность связанных между собой объектов (вершин). Вершины связываются ребрами графа. Граф бывает как направленным, так и нет. В направленном графе у ребра, соединяющего две вершины существует и направление связи от какой вершины к какой. В каждую вершину могут «входить» одно или несколько ребер и «выходить» одно или несколько.
Для не направленных графов существует просто соединение вершин.
Петля — это когда производишь переход от одной вершины к другой возможно вернуться в исходную вершину.
Цикл это когда переходя от вершины к вершине по ребрам ВСЕГДА возвращаешься в исходную вершину.
Жертва ЕГЭПрофи (658) 6 лет назад
Хорошо начали, но в конце даже я запутался.
OK, пусть ориентированные графы нас не интересуют. На простом языке:
Петля — ребро, концами которого является одна и та же вершина.
Цикл — любой замкнутый путь, то есть конечная последовательность вершин, в которой две любые соседние соединены ребром, и в которой начальная и конечная вершины совпадают.
По сути, петля — тоже цикл, просто очень коротенький: -)
1. Информационные модели на графах
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними — отрезками или дугами.
Основы теории графов как математической науки заложил в \(1736\) г. Леонард Эйлер , рассматривая задачу о Кёнигсбергских мостах. Сегодня эта задача стала классической.
Графом называется конечное множество точек, некоторые из которых соединены линиями.
Обрати внимание!
Точки называются вершинами графа, а соединяющие линии — рёбрами.
Количество рёбер, выходящих из вершины графа, называется степенью вершины .
Обрати внимание!
Вершина графа, имеющая нечётную степень, называется нечётной, а чётную степень — чётной.
Изолированная вершина — вершина, степень которой равна \(0\).
Конечная вершина графа — вершина, степень которой равна \(1\).
Направленная линия (со стрелкой) называется дугой .
Линия ненаправленная (без стрелки) называется ребром .
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлёй .
Рассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является двусторонним, поэтому вершины соединены линиями без стрелок.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Граф, в котором все вершины соединены рёбрами, называется неориентированным .
Цепь — путь по вершинам и рёбрам, включающий любое ребро графа не более одного раза.
Цикл — цепь, начальная и конечная вершины которой совпадают.
Граф с циклом называют сетью .
Ориентированный граф — граф, рёбрам которого присвоено направление.
С помощью таких графов могут быть представлены схемы односторонних отношений.
Если все вершины графа чётные, то можно одним росчерком пера начертить граф. При этом начать движение можно с любой вершины и закончить в той же вершине.
Граф с двумя нечётными вершинами также можно начертить одним росчерком. Начинать движение надо с одной нечётной вершины, а заканчивать в другой.
Что такое петля в информатике
Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Если ребра не имеют ориентации, граф называется неориентированным.
Граф
Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра — линиями, соединяющими точки (рис. 2.15).
Петля это дуга, начальная и конечная вершина которой совпадают.
Простой граф граф без кратных ребер и петель.
Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.
ПУТИ, МАРШРУТЫ, ЦЕПИ и ЦИКЛЫ.
Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn — концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.
Маршрут в графе путь, ориентацией дуг которого можно пренебречь.
Цепь маршрут, в котором все ребра попарно различны.
Цикл замкнутый маршрут, являющийся цепью.
Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.
Граф отношения делимости
Построим граф, изображающий отношение делимости на множестве . Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое (рис. 2.16).
ПОДГРАФЫ
Подграф графа это граф, являющийся подмоделью исходного графа, т.е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).
Подграф, порожденный множеством вершин U это подграф, множество вершин которого — U, содержащий те и только те ребра, оба конца которых входят в U.
Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.
Связность графа
Граф называется связным, если любая пара его вершин связана.
Связными компонентами графа называются подграфы данного графа, вершины которых связаны.
Деревья
Дерево — это связный граф без циклов.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья.
Генеалогическое дерево
На рисунке 2.17 показано библейское генеалогическое дерево.
Граф без цикла называется лесом. Вершины степени 1 в дереве называются листьями.
Деревья — очень удобный инструмент представления информации самого разного вида.
Деревья отличаются от простых графов тем, что при обходе дерева невозможны циклы. Это делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятия дерева активно используется в информатике и программировании.
Очевидно, что графический способ представления графов непригоден для ПК. Поэтому существуют другие способы представления графов.
В теории графов применяются
Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующнго рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит — 1 в строке, соответствующей вершине х и 1, в строке, соответствующей вершине у. Во всех остальных 0. Петлю, т.е. дугу (х,х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствуюший ребру (х,у) содержит 1, соответствующие х и у и нули во всех остальных строках.
Матрица смежности. Это матрица n×n где n — число вершин, где b ij = 1, если существует ребро, идещее из вершины х в вершину у и b ij = 0 в противном случае.
Составим матрицы инциндентности и смежности для следующего непрерывного графа (рис. 2.18)
1. Определения и простейшие свойства графов
Графы используют во всех отраслях нашей жизни. Знание основ теории графов необходимо в управлении производством, бизнесе, при построении путей транспортировки и доставки, решении задач.
Графы используют в связи с развитием теории вероятности, математической логики и информационных технологий.
Граф — это конечная совокупность вершин , некоторые из которых соединены ребрами , т.е. это совокупность точек, называемых вершинами , и линий, соединяющих некоторые из вершин, называемых ребрами или дугами в зависимости от вида графа.
Мультиграф — это граф, у которого пара вершин соединены несколькими ребрами. А такие ребра, которые соединяют одну и ту же пару вершин, называют кратными . Две различные вершины графа, соединенные ребром, называются смежными .
Ребро не всегда соединяет разные вершины.
Петля — это ребро, которое соединяет вершину саму с собой.
Рис. 1
На рисунке 1 изображен мультиграф со смежными ребрами (выделены черным цветом), кратными ребрами (выделены красным) и петлями (выделены синим) .
Степенью вершины называют количество ребер, выходящих из одной вершины. Для петли ребро выходит из вершины дважды. Обозначать степень вершины \(а\) будем как γ ( а ) .
На рисунке 2 изображен граф с 7 вершинами.
Рис. 2
Составим список степеней вершин этого графа: γ ( a ) = 1, γ ( b ) = 5, γ ( c ) = 2, γ ( d ) = 2, γ ( e ) = 3, γ ( f ) = 2, γ ( g ) = 1 .
Свойства графов :
В любом графе есть, по крайней мере, две вершины, имеющие одинаковую степень.
Для любого графа количество вершин нечетной степени всегда будет четное.
Сумма степеней всех вершин графа равна удвоенному числу его ребер.
Маршрут на графике — это последовательность ребер a 1 , a 2 , . a n , в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра.
Для графа, изображенном на рисунка 2, a 1 , a 2 , a 3 , a 7 , a 1 , a 5 — маршрут, a 6 , a 3 , a 7 — циклический маршрут, а последовательность a 7 , a 6 , a 2 , a 1 , a 4 — маршрутом не является.
Рис. 2
Цепь — это маршрут, в котором каждое ребро содержится не более одного раза. Цепь, являющаяся циклическим маршрутом, называется циклом .
Для графа, изображенном на рисунка 2, a 1 , a 2 , a 6 , a 7 , a 4 , a 5 , a 7 — цепь, a 2 , a 6 , a 7 , a 8 , a 4 , a 2 , a 6 — цикл.
Цепь называется простой , если проходит через каждую свою вершину ровно один раз. Цикл называется простым , если является простой цепью.
Для графа, изображенном на рисунка 2, a 1 , a 2 , a 6 , a 7 , a 4 — простая цепь, a 2 , a 6 , a 7 , a 8 , a 4 — простой цикл.
Связанные верши ны — это вершины \(a\) и \(b\), для которых существует цепь, начинающаяся в \(a\) и заканчивающаяся в \(b\).
Связный граф — это граф, у которого любые две вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом).
Один и тот же граф может быть изображен по-разному. Например, граф на рисунке 2 тот же, что и изображен на рисунке 3.