Графы и их элементы - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Графы и их элементы. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Основные понятия и определения графа и его элементов

Слайд 2

Описание слайда:

Графом G = (V, X) называется пара двух конечных множеств: множество точек и множество линий X, соединяющих некоторые пары точек. В терминах декартова произведения подмножество множества V´V: XÌV´V. Точки называются вершинами или узлами графа, линии — ребрами графа

Слайд 3

Описание слайда:

Пусть дан граф G = (V, X), где v = [V, W, ...} — конечное непустое множество его вершин, а Х(V, W) — его ребра. Если ребро графа G соединяет две его вершины V и W (т.е. ÎX), то говорят, что это ребро им инцидентно. Пусть дан граф G = (V, X), где v = [V, W, ...} — конечное непустое множество его вершин, а Х(V, W) — его ребра. Если ребро графа G соединяет две его вершины V и W (т.е. ÎX), то говорят, что это ребро им инцидентно. Две вершины графа называются смежными, если существует инцидентное им ребро. Если граф G имеет ребро Х(V, W), у которого начало и конец совпадают, то это ребро называется петлей. Два ребра называются смежными, если они имеют общую вершину.

Слайд 4

Описание слайда:

Граф G( V, X) может иметь ребра с одинаковыми парами вида Х(V, W). Такие ребра называются кратными, или параллельными. Граф G( V, X) может иметь ребра с одинаковыми парами вида Х(V, W). Такие ребра называются кратными, или параллельными. Количество одинаковых пар вида Х(V, W) называется кратностью ребра (V, W). Вершина графа, имеющая степень, равную нулю, называется изолированной. Граф, состоящий из изолированных вершин, называется нуль-графом. Вершина графа, имеющая степень, равную 1, называется висячей.

Слайд 5

Описание слайда:

Теорема 1. В графе G(V,Х) сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа: где п = ïVï — число вершин; т = ïХï — число ребер графа. Вершина называется четной (нечетной ) если ее степень четное (нечетное) число.

Слайд 6

Описание слайда:

Теорема 2. Число нечетных вершин любого графа — четно. Следствие.Невозможно начертить граф с нечетным числом нечетных вершин.

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Если все пары (Vi , Vj) во множестве X являются упорядоченными, т.е. кортежами длины 2, то граф называется ориентированным, орграфом, или направленным. Если все пары (Vi , Vj) во множестве X являются упорядоченными, т.е. кортежами длины 2, то граф называется ориентированным, орграфом, или направленным. Началом ребра называется вершина, указанная в кортеже первой, концом— вторая вершина этой пары (графически она указана стрелкой). Ребра ориентированного графа имеют определенные фиксированные начало и конец и называются дугами. Степенью-входа (выхода) вершины ориентированного графа называется число ребер, для которых эта вершина является концом (началом). Дуги орграфа называются кратными, если они имеют одинаковые начальные и конечные вершины, т.е. одинаковые направления.

Слайд 9

Описание слайда:

Последовательность попарно инцидентных вершин Vi1 , Vi2, ..., V ik неориентированного графа, т.е. последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом. Последовательность попарно инцидентных вершин Vi1 , Vi2, ..., V ik неориентированного графа, т.е. последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом. Число ребер маршрута называется длиной маршрута. Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом. Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами при условии, что существует хотя бы один такой маршрут. В маршруте одно и то же ребро может встретиться несколько раз. Если ребро встретилось только один раз, то маршрут называется цепью.

Слайд 10

Описание слайда:

В орграфе маршрут является ориентированным и называется путем. Другими словами, путь— упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны. В орграфе маршрут является ориентированным и называется путем. Другими словами, путь— упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны. Цикл в орграфе — путь, у которого совпадают начало и конец. Цепь, путь и цикл в графе называются простыми, если они проходят через любую из вершин не более одного раза. Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут. Две вершины называются связными, если существует маршрут между ними. Граф G можно разбить на непересекающиеся подмножества Хi по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств — несвязны. Тогда все подграфы Vi(классы эквивалентности) графа G называют связными компонентами, или компонентами связности.Связный граф имеет одну компоненту связности.

Слайд 11

Описание слайда:

Теорема 3. Для того чтобы связный граф G являлся простым циклом, необходимо и достаточно, чтобы каждая его вершина имела степень, равную 2.

Слайд 12

Описание слайда:

Ребро (V, W) связного графа G называется мостом, если после его удаления G станет несвязным и распадется на два связных графа G ' и G ". На рисунке мост (СЕ) разделил связный граф G7 на два различных связных графа: G ' с вершинами (А,В, С,D) и G " с вершинами (Е, F, G,Н,I). Также мостом является ребро ЕС. Ребро (V, W) связного графа G называется мостом, если после его удаления G станет несвязным и распадется на два связных графа G ' и G ". На рисунке мост (СЕ) разделил связный граф G7 на два различных связных графа: G ' с вершинами (А,В, С,D) и G " с вершинами (Е, F, G,Н,I). Также мостом является ребро ЕС.

Слайд 13

Описание слайда:

Теорема 4. Ребро графа является мостом тогда и только тогда, когда не принадлежит ни одному циклу.

Слайд 14

Описание слайда:

Графы G' и G" называются изоморфными, если существует взаимно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вершины. Графы G' и G" называются изоморфными, если существует взаимно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вершины. Графы G1 (V1 , Х2) и G2( V2, Х2) называются изоморфными,если | V1| = |V2| = п и существует подстановка sÎSn, такая, что V2 = s(V1), а Х2 = {s (Vi); s( Vj)) ï (Vi, Vj)Î Х1}. Граф G называется планарным (плоским),если существует изоморфный ему граф G', в изображении которого на плоскости ребра пересекаются только в вершинах. Областью называется подмножество плоскости, пересекающееся с планарным графом только по некоторому проcтому циклу графа, являющемуся границей области.

Теги Графы элементы

Похожие презентации