Графы и их представление на ЭВМ - презентация, доклад, проект скачать

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

Графы и их представление на ЭВМ, слайд №1

Графы и их представление на ЭВМ, слайд №2

Графы и их представление на ЭВМ, слайд №3

Графы и их представление на ЭВМ, слайд №4

Графы и их представление на ЭВМ, слайд №5

Графы и их представление на ЭВМ, слайд №6

Графы и их представление на ЭВМ, слайд №7

Графы и их представление на ЭВМ, слайд №8

Графы и их представление на ЭВМ, слайд №9

Графы и их представление на ЭВМ, слайд №10

Графы и их представление на ЭВМ, слайд №11

Содержание ▲

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

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

Слайд 1

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

Тема: «Графы и их представление на ЭВМ» Студентки группы КСК-921 Миркачевой Марии

Слайд 2

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

Основное определение Графом G(V, Е) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элемен тов множества V (Е — множество ребер). G ( V , E ) =  V, E, V  , E  VV, E = E- Соединения между узлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могут быть присвоены определенные веса или метки.

Слайд 3

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

Смежность Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью вершины. Если степень вершины равна 0, то получается изолированная графа. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называется мультиграфом.

Слайд 4

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

Другие определения Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами. Если элементом множества Е может быть пара одинаковых (не различных)элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом). Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мулътиграфом. Если элементами множества Е являются не обязательно двухэлементные, алюбые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом. Если задана функция Е: V  М и/или F: Е М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным).В качестве множества пометок обычно используются буквы или целые числа.

Слайд 5

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

Виды графов и операции над ними Элементы графов Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G'  G), если V'  V и/или Е'  Е. Если V' = V, то G ' называется остовным подграфом G. Если V'  V & Е'  Е & (V'  V  Е'  Е), то граф G ' называется собственным подграфом графа G. Подграф G'(V' , Е') называется правильным подграфом графа G(V,Е), если G ' содержит все возможные ребра G:  и,v  V' (и, v)  Е  (и, v)  Е'. Правильный подграф G '(V ' , Е') графа G (V, Е) определяется подмножеством вер шин V '. Маршрутом в графе называется чередующаяся последовательность вершин и ребер в которой любые два соседних элемента инцидентны. v0, e1, v1, e2, v2,…,ek, vk, Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер. Если v0 = vk, то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи v0, e1, v1, e2, v2,…,ek, vk, вершины v0 и vk, называются концами цепи. Говорят, что цепь с концами и и v соединяет вершины и и v. Цепь, соединяющая вершины и и v, обозначается (и, v). Очевидно, что если есть цепь, соединяющая вершины и и v, то есть и простая цепь, соединяющая эти вершины. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.

Слайд 6

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

Виды графов и операции над ними Изоморфизм графов Говорят, что два графа G1(V1 , Е1) и G2(V2 , Е2) изоморфны (обозначается G1 ~ G2), если существует биекция h: V1  V2, сохраняющая смежность: e1 = ( u , v )  E1  e2 = ( h( u ), h( v ) )  E2, e2 = ( u , v )  E2  e1 = ( h-1( u ), h-1( v ) )  E1 Изоморфизм графов есть отношение эквивалентности. Действительно, изомор физм обладает всеми необходимыми свойствами: рефлексивность: G ~ G, где требуемая биекция суть тождественная функция; симметричность: если G1 ~ G 2 с биекцией h, то G 2 ~ G 1 с биекцией h-1; транзитивность: если G1 ~ G 2 с биекцией h, и G 2 ~ G 3 с биекцией g, тоG 1 ~ G 3 с биекцией g  h.

Слайд 7

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

Виды графов и операции над ними Тривиальные и полные графы Граф, состоящий из одной вершины, называется тривиальным. Граф, состоящий из простого цикла с k вершинами, обозначается Сk. Пример С3 — треугольник. Граф, в котором каждая пара вершин смежна, называется полным. Полный граф с р вершинами обозначается Кр, он имеет максимально возможное число ребер: Полный подграф (некоторого графа) называется кликой (этого графа).

Слайд 8

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

Виды графов и операции над ними Двудольные графы Двудольный граф (или биграф, или четный граф) — это граф G(V,Е), такой что множество V разбито на два непересекающихся множества V1 и V2 (V1 V2 = V V1  V2) причем всякое ребро из Е инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из V2). Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом. Если | V1 | = m и | V1 | = п, то полный двудольный граф обозначается Km,n

Слайд 9

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

Представление графов в ЭВМ Конструирование структур данных для представления в программе объектов математической модели — это основа искусства практического программирования. Используется четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо.

Слайд 10

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

Требования к представлению графов Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики п(р, q) — объема памяти для каждого представления. Здесь р - число вершин, а q - число ребер. Указанные представления пригодны для графов и орграфов, а после некоторой модификации также и для псевдографов, мультиграфов и гиперграфов. 1. Матрица смежности. Представление граф с помощью квадратной булевской матрицы, отражающей смежность вершин, называется матрицей смежности, M : array [1..p, 1..p] of 0..1, M [i, j] = 1, если вершина vi смежна с вершиной vj 0, если вершины не vi и vj смежны. Для матрицы смежности п(р, q) = O(p2).

Слайд 11

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

. 2. Матрица инциденций. Представление графа с помощью матрицы H : array [1..p, 1..q] of 0..1 (для орграфов H : array [1..p, 1..q] of -1..1), отражающей инцидентность вершин и рёбер, называется матрицей инциденций, где для неориентированного графа H [i, j] = 1, если вершина vi инцидентна ребру ej, 0, в противном случае. а для ориентированного графа 1, если вершина vi инцидентна ребру ej и является его концом, H [i, j] = 0, если вершина vi и ребро ej не инцидентны, -1, если вершина vi инцидентна ребру ej и является его началом 3. Списки смежности. Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей Г : array [1..р] оf  N на списки смежных вершин (элемент списка представлен структурой N : record v: 1..р; п :  N endrecord), называется списком смежности. В случае представления неориентированных графов списками смежности п(р, q) = О(р + 2q), а в случае ориентированных графов п(р, q) = О(р + q). 4. Массив дуг. Представление графа с помощью массива структур Е : array [1..р] of record b,e : 1..p endrecord, отражающего список пар смежных вершин, называется мас сивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) п(р, q) = О( 2q). 5. Обход графа — это некоторое систематическое перечисление его вершин (и/или ребер). Наибольший интерес представляют обходы, использующие локальную информацию (списки смежности). Среди всех обходов наиболее известны поиск в ширину и в глубину. Алгоритмы поиска в ширину и в глубину лежат в основе многих конкретных алгоритмов на графах.

Теги Графы представление

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