Студопедия

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

Разделы сайта

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






  • Графы и деревья. Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно






    Граф - это двойка < V, E >, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между «началом» и «концом» ребра.

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

    Если ребра графа определяются упоря­доченными парами вершин, то такой граф называют ориентированным – орграфом (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указы­вающую его направление).

     

    Если порядок ребер не имеет значения, то граф называется неориентированным.

    Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (например, ребра е 4 и е5). Если начало и конец ребра совпадают, то такое ребро называется петлей (например, ребро e7).

    Граф без петель и параллель­ных ребер называется простым.

    Если ребро ек определяется вершинами vi и vj (будем обозначать этот факт следующим образом: еk = (vi, vj), то говорят, что ребро ек инцидентно вершинам vi и vj.

    Граф G(E, U) называется конечным, если множество Е вершин конечно. Граф G(E, U), у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколь­кими ребрами, то такой граф называется мультиграфом. Две верши­ны еi, еj Î Е называются смежными, если они соединены ребром. Чис­ло ребер, инцидентных данной вершине еi, называется локальной степенью этой вершины р(еi). Число ребер r графа G(E, U) определя­ется выражением

    Множества вершин и ребер части графа являются подмножества­ми вершин и ребер исходного графа

    Полным графом называется граф у которого каждая вер­шина соединена ребрами с остальными вершинами

    Обязанность графов

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

    Две вершины еi и еj называются связанными, если существует мар­шрут из еi в еj.

    Компонентой связности графа называется подмножество его вер­шин с инцидентными им ребрами, такое, что любая вершина свя­зана с любой другой вершиной маршрута. Например, из графа на рис. 3.5 можно выделить следующие две компоненты связанности, показанные сплошной линией.

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

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

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






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.