Произвольная структура глобальной компьютерной сети в виде графа

Обновлено: 07.07.2024

Глобальная сеть используется как транзитный транспортный механизм, предоставляющий только услуги трех нижних уровней модели OSI.

При построении корпоративной сети данные хранятся и вырабатываются в компьютерах, принадлежащих локальным сетям этого предприятия, а глобальная сеть их только переносит из одной локальной сети в другую.

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

Функции глобальной сети, относящиеся к верхним уровням стека протоколов, играют значительную роль в вычислительных сетях. Это связано с предоставлением высокоуровневых услуг Internet (широковещательное распространение звукозаписей, организация интерактивных «бесед» - chat, организация конференций по интересам (служба News), поиск информации и ее доставка и многое другое.).

Информационные услуги Internet оказали влияние на традиционные способы доступа к разделяемым ресурсам.

Появился специальный термин - intranet, который применяется в тех случаях, когда технологии Internet переносятся в корпоративную сеть.

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

В результате глобальные и локальные сети постепенно сближаются за счет взаимопроникновения технологий разных уровней - от транспортных до прикладных.

Типичный пример структуры глобальной компьютерной сети приведен на (рис. 6.2.)

Рис. 6.2Пример структуры глобальной сети

Здесь используются следующие обозначения:

S (switch) - коммутаторы,

R (router) - маршрутизаторы,

MUX (multiplexor)- мультиплексор,

UNI (User-Network Interface) - интерфейс пользователь - сеть

NNI (Network-Network Interface) - интерфейс сеть - сеть.

Кроме того, офисная АТС обозначена аббревиатурой РВХ, а маленькими черными квадратиками - устройства DCE,о которых будет рассказано ниже.

Сеть строится на основе некоммутируемых (выделенных) каналов связи, которые соединяют коммутаторы глобальной сети между собой. Коммутаторы называют также центрами коммутации пакетов (ЦКП), то есть они являются коммутаторами пакетов, которые в разных технологиях глобальных сетей могут иметь и другие названия - кадры, ячейки cell.

Абоненты сети подключаются к коммутаторам в общем случае также с помощью выделенных каналов связи. Эти каналы связи имеют более низкую пропускную способность.

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

Конечными узлами глобальной сети являются:

отдельные компьютеры К,

мультиплексоры MUX, которые используются для одновременной передачи по компьютерной сети данных и голоса (или изображения).

Все эти устройства вырабатывают данные для передачи в глобальной сети, поэтому являются для нее устройствами типа DTE (Data Terminal Equipment).

Локальная сеть отделена от глобальной маршрутизатором или удаленным мостом (который на рисунке не показан), поэтому для глобальной сети она представлена единым устройством DTE - портом маршрутизатора или моста.

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

Так как конечные узлы глобальной сети должны передавать данные по каналу связи определенного стандарта, то каждое устройство типа DTE требуется оснастить устройством типа DCE (Data Circuit terminating Equipment) которое обеспечивает необходимый протокол физического уровня данного канала.

В зависимости от типа канала для связи с каналами глобальных сетей используются DCE трех основных типов:

1. модемы для работы по выделенным и коммутируемым аналоговым каналам,

2. устройства DSU/CSU для работы по цифровым выделенным каналам сетей

3. терминальные адаптеры (ТА) для работы по цифровым каналам сетей ISDN.

Связь компьютера или маршрутизатора с цифровой выделенной линией осуществляется с помощью пары устройств, обычно выполненных в одном корпусе или же совмещенных с маршрутизатором. Этими устройствами являются: устройство обслуживания данных (УОД) и устройство обслуживания канала (УОК). В англоязычной литературе эти устройства называются соответственно Data Service Unit (DSU) и Channel Service Unit (CSU). DSU преобразует сигналы, поступающие от DTE (обычно по интерфейсу RS-232C, RS-449 или V.35). DSU выполняет синхронизацию, формирует кадры каналов, усиливает сигнал и осуществляет выравнивание загрузки канала. CSU выполняет более узкие функции, в основном это устройство занимается созданием оптимальных условий передачи в линии. Эти устройства, как и модуляторы-демодуляторы, часто обозначаются одним словом DSU/CSU

Устройства DTE и DCE обобщенно называют оборудованием, размещаемым на территории абонента глобальной сети - Customer Premises Equipment, CPE.

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

Любые сети состоят из отдельных участников (людей или вещей в сети) и отношений между ними. Сети очень часто визуализируются с помощью графов – структур, состоящих из множества точек и линий, отображающих связи между этими точками. Участники представлены в виде узлов сети, а их отношения представлены в виде линий, их связывающих. Такая визуализация помогает получить качественную и количественную оценку сетей:

Рис. 1. Направленный граф, изображающий денежный оборот между банками, формирующими валютный рынок (1). Красным отмечены банки ЕС, синим – Северной Америки, зелёным – других стран.

Рис. 2. Граф, отображающий сотрудничество партнеров по аудиту в Дании в 2010-2014 гг (2)

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

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

Кроме того, на примере сетей можно и прогнозировать события. К примеру, существуют модели, которые оценивают вероятность сбоя программного обеспечения, некоторые из них рассматривают людей как источник для прогнозов – ведь именно люди разрабатывают и тестируют продукты до релиза. Их взаимодействия образуют сеть: можно представить разработчиков как узлы, а то, работали ли они вместе над одним и тем же файлом в рамках одного релиза, как рёбра сети. Понимание взаимодействий и информация о ранее произошедших сбоях позволит многое сказать о надёжности конечного продукта и укажет на файлы, в которых риск сбоя наиболее вероятен.

Теперь попробуем применить анализ социальных сетей на практике. Для этого мы будем использовать язык программирования Python, а точнее библиотеку networkx, предназначенную для работы с графами, библиотеку matplotlib для визуализации и библиотеку community для выделения сообществ внутри сети. Давайте их импортируем:

1. Импорт данных и преобразование их в граф

В приведённом выше коде датасет был импортирован и преобразован в граф. Затем мы последовательно вывели основные параметры графа: количество узлов, рёбер и среднее количество соседей у узлов в графе. Последний параметр отражает, насколько тесно связаны узлы между собой.

2. Основные характеристики графов

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

Прежде всего рассмотрим понятия связности и направленности. Граф называется связным, если каждая пара узлов графа связана между собой, т.е. из любого узла можно прийти в любой другой узел. Если же граф несвязный, то его можно разбить на максимально связные подграфы (называемые компонентами). Также графы могут быть направленными и ненаправленными. Это определяется наличием направленности связей между двумя участниками. Одним из примеров направленной сети являются транзакции между клиентами банка, где у каждого клиента могут быть как входящие, так и исходящие платежи.

В общем случае в направленных графах связи не взаимны, поэтому для направленных графов вместо понятия связности выделяют понятия компоненты слабой и сильной связности. Компонента считается слабо связной, если при игнорировании направления получается связный граф. Компонента сильной связности может быть таковой, если все её вершины взаимно достижимы. Давайте посмотрим, какой структурой обладает граф из нашего датасета с электронной перепиской:

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

Здесь мы провели проверку на направленность и связность графа и выяснили, что граф из датасета является направленным и содержит несколько несвязных компонент. Давайте попробуем посмотреть поближе на самые крупные компоненты сильной и слабой связности:

Итак, мы получили основные характеристики для компоненты слабой связности и для входящей в неё компоненты сильной связности. Давайте посмотрим, какие выводы мы можем сделать на этом этапе. Мы видим, что из 1005 участников друг с другом общаются 986 человек, при этом 183 человека из них отправляли электронные письма другим людям в одностороннем порядке, и только 803 человека поддерживали двустороннее общение. В 823 случаях попытка наладить коммуникацию посредством электронной почты оказалась провальной. Также мы видим, что наиболее активные участники (входящие в компоненту сильной связности) поддерживают коммуникацию в среднем с 30 людьми.

Кроме того, узлы и связи могут создавать различные типы сетей: однодольные, двудольные или многоуровневые. Однодольные сети состоят из одного типа участников и связей между ними. Двудольные сети состоят из двух разных типов участников, где один из типов узлов связан только с другим типом. Многоуровневые сети также включают два типа участников, однако связи могут соединять как участников разных типов, так и однотипных участников (например, отношения между менеджерами и отношения между проектами). Взятый нами для исследования датасет представляет собой сеть однодольного типа, так как состоит только из одного типа участников и связей между ними.

3. Визуализация графа

А теперь давайте попробуем визуализировать взятый нами датасет. Для этого нам понадобится библиотека matplotlib, уже импортированная нами выше:

В первой строке задаётся размер будущего изображения, которому затем присваивается определённое название. В третьей строке функции draw передаётся граф и указывается размер узлов, после чего граф выводится на экран. Давайте на него посмотрим:

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

Давайте также рассмотрим граф, иллюстрирующий компоненту сильной связности – людей, которые поддерживают двустороннюю коммуникацию с другими участниками исследовательского учреждения:

4. Степень узла и распределение степеней узлов

Теперь, когда мы знаем структуру нашего графа и умеем его визуализировать, давайте перейдём к более детальному анализу. У каждого узла в графе есть степень – количество ближайших соседей этого узла. В направленных сетях можно различать как степень входа (количество входящих связей с узлом), так и степень выхода (количество исходящих связей с узла). Если для каждого узла графа посчитать степень, можно определить распределение степеней узлов. Давайте посмотрим на него для графа с электронной перепиской:

5. Путь, диаметр и среднее расстояние в графе

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

Любая последовательность ребер, которая соединяет узлы, называется путь. Чаще всего в исследованиях рассматривается простой путь, то есть путь без циклов и повторяющихся узлов. Кратчайший путь между двумя узлами называют геодезическим расстоянием. Самый длинный кратчайший путь в графе называют его диаметром, однако он очень чувствителен к отклонениям (одна цепочка в многомиллионном графе может изменить его диаметр). В направленных графах понятие диаметра можно применить только для компоненты сильной связности, ведь для подсчёта диаметра необходимо, чтобы для каждой пары узлов существовал путь между ними. В ненаправленных графах достаточно того, чтобы рассматриваемая компонента была связной.

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

Давайте разберём полученные результаты. Диаметр в данном случае показывает нам максимальное расстояние между двумя незнакомыми людьми, и здесь, как и в известной теории о шести рукопожатиях, это расстояние равно 6. Среднее расстояние в компонентах также невелико, в среднем двум незнакомым людям достаточно 2 «рукопожатий». Здесь можно также увидеть интересный феномен: среднее расстояние в компоненте сильной связности несколько ниже, чем в компоненте слабой связности. Объяснить это можно тем, что для компоненты слабой связности не учитывается направленность связей (только сам факт её наличия). Из-за этого связь в слабой компоненте появляется там, где она отсутствовала для сильной компоненты.

6. Кластеризация и выделение сообществ

C расстояниями между участниками разобрались, давайте перейдём к другим явлениям, отражающим, насколько участники в графе связаны между собой: кластеризации и сообществам.

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

Для графов с высокой степенью кластеризации характерно присутствие значительного количества связанных троек (трёх узлов, связанных друг с другом). Они являются строительным блоком многих социальных сетей, где количество подобных треугольников очень велико. Часто возникают даже не треугольники, а целые кластерные образования, называемые сообществами, которые связаны между собой теснее, чем с остальным графом.

Посмотрим на кластеризацию и кластерный коэффициент для компоненты слабой связности:

Для компоненты сильной связности мы можем получить те же характеристики, а также определить количество центральных узлов (узлов, которые сильнее всего связаны с остальными) и количество узлов на периферии графа:

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

Итак, в графе с электронной перепиской можно выделить 8 сообществ, которые связаны между собой теснее, чем с остальным графом. Самое маленькое из сообществ содержит 54 участников, а самое крупное – 188 участников. Для сетей, содержащих перекрывающиеся или вложенные сообщества, определить оптимальное разбиение может оказаться сложнее. Поэтому при каждом запуске кода состав сообществ может различаться. Посмотрим визуализацию для полученного нами разбиения:

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

7. Взаимность связей

Кроме уже описанных свойств также существует такое понятие, как взаимность в направленной сети. Эта характеристика описывает, какой процент исходящих связей имеет обратную, входящую, связь. Для того, чтобы это узнать, используем специальную функцию overall_reciprocity библиотеки networkx и посмотрим на уровень взаимности в графе и его компонентах:

8. Универсальные свойства сетей

Распределение степеней узлов. Во всех сетях есть много узлов с низкой степенью, в то же время есть небольшое количество огромных узлов, у которых соседей очень много. Это логично: если мы посмотрим на ссылки между различными web-сайтами, то обнаружим, что существует небольшое количество крупных сайтов, на которые в большом количестве ссылаются все остальные (Wikipedia, Microsoft). В то же время на среднестатистические сайты ссылки встречаются гораздо реже, хотя большинство сайтов относятся именно к такому типу.
Диаметр и среднее расстояние в графе. Крупные сети имеют такое устройство, что средний диаметр у них очень небольшой, это явление в анализе социальных сетей называется явлением «малого мира». Оно хорошо описывается через теорию шести рукопожатий: несмотря на огромное количество людей, среднее расстояние между двумя незнакомыми людьми будет равным шести.
В больших сетях, как правило, присутствуют гигантские связные компоненты: более 80% узлов связаны между собой, остальные представлены более мелкими компонентами. При этом в каждой из крупных компонент можно встретить сообщества – группы объектов, которые связаны между собой теснее, чем с остальным графом. Наличие кластеризации, то есть большого количества таких сообществ, чрезвычайно распространено в социальных графах.
Во многих социальных графах действует принцип взаимности, когда при наличии исходящей связи очень высока вероятность встретить и входящую связь. Эта концепция специфична для направленных сетей, поскольку взаимность и обмен являются фундаментальными социальными процессами.

Примечания

С полным текстом исследования можно ознакомиться в книге Николая Викторовича Урсул «Вся правда о Forex» (2019).

Исследование описано в статье «The Application of Social Network Analysis to Accounting and Auditing» Slobodan Kacanski, Dean Lusher (2017, ссылка).

Презентация на тему: " Структура данных: Деревья, сети, графы, таблицы Разработала учитель информатики МБОУ «СОШ 5 г.Азнакаево» РТ Габдуллина Ф. М." — Транскрипт:

1 Структура данных: Деревья, сети, графы, таблицы Разработала учитель информатики МБОУ «СОШ 5 г.Азнакаево» РТ Габдуллина Ф. М.

2 Граф - отображает элементный состав системы и структуру связей Описание некоторой местности: «Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино. Д Р КМ Б Это не карта местности. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом. Составными частями графа являются вершины и ребра. вершины ребра Неориентированный граф

3 Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин Д Р КМ Б Неориентированный граф (сеть) Как добраться из Р в М ? 1)Р-К-Б-М 2) Р-К-Д-Б-М Для сетей также характерно наличие замкнутых путей, который называются циклами Цикл К-Д-Б-К

4 Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Граф с такими свойствами называется ориентированным. Существует четыре группы крови человека. При переливании не все группы совместимы. Данный граф показывает возможные варианты переливания крови. Например, из графа видно,что кровь I группы можно переливать любому человеку. IV I IIIII Направленные линии называют дугами (в отличии от ребер неориентированных графов). Линию, выходящую и входящую в одну и ту же вершину называют петлей. Ориентированный граф Дуги Петли

5 Иерархическая структура Директор Заместители директора Учителя Ученики Система административного управления, между элементами которой установлены отношения подчиненности.

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

7 Примеры иерархических структур - деревьев Владимир Рюрик Игорь Святослав Олег Ярополк Мстислав Тмутараканский ГлебЯрославБорис Святополк Изяслав Полоцкий

8 Таблицы Средства ЭОРКол-во учителей в % Интерактивные лекции 63% Виртуальные экскурсии 93% Виртуальные лаборатории 41% Конструкторы формул/графиков 33% Игровые модули 67% Контрольные модули 96% Тренажеры для оттачивания различных навыков 81% В какой форме представлена информация? Табличный способ представления данных является универсальным

9 Таблица типа "объект-свойство" Датаосадкитемп 15.03снег дождь- 20 Таблица типа "объект-объект" Ученикрусскийалгебра Иванов44 Сидоров53 Таблица типа «двоичная матрица» УченикТанцыЛегкая атлетика Сидорова10 Иванов01

10 Д Р КМ Б Поселок БабкиноДедкиноКошкиноРепкиноМышкино Бабкино01101 Дедкино10100 Кошкино11010 Репкино00100 Мышкино10000 Какая связь между графом и таблицей ? Попробуйте представить информацию о дорожной связи между поселками в форме таблицы.

11 Д Р КМ Б Поселок БабкиноДедкиноКошкиноРепкиноМышкино Бабкино01101 Дедкино10100 Кошкино11010 Репкино00100 Мышкино10000 Если сеть является неориентированным графом, то матрица смежности симметрична относительно главной диагонали. Матрица смежности

12 Попробуйте представить информацию о группах крови в форме таблицы. Начальная вершина Конечная вершина IIIIIIIV I1111 II0101 III00110 IV0001 У матрицы, отражающий ориентированный граф, симметричности не будет

13 Зачем мы переводили графы в табличную форму? Вам понятнее граф или таблица? С точки зрения человека, граф гораздо нагляднее и понятнее представляет структуру системы, чем таблица. А компьютеру какую форму обрабатывать легче? Для компьютерной обработки табличная форма подходит лучше. Многие компьютерные технологии (базы данных, электронные таблицы) работают с таблицами и поэтому в компьютерном моделировании чаще работают с табличным представлением.

14 Подведем итоги Структуры данных ГрафыТаблицы ДеревьяСетиТипы таблиц Элементы дереваЭлементы сети Объект-свойство Объект-объект Двоичная матрица КореньВетвиЛистьяВершиныРебра Единственность пути между вершинами Множественность путей между вершинами

15 Выполните задания 1. Нарисуйте два варианта графа системы «Компьютер», содержащего следующие вершины: процессор, оперативная память, внешняя память, клавиатура, монитор, принтер; а) линия связи обозначает отношение «передает информацию»; б) линия связи обозначает отношение «управляет».

16 Выполните задания 2. Нарисуйте произвольную структуру глобальной компьютерной сети в виде графа, в котором вершины обозначают серверы, а ребра – линии связи. Опишите эту сеть в виде двоичной матрицы смежности.

17 Выполните задания 3. Нарисуйте родословное дерево своей семьи (только по мужской линии или только по женской) с наибольшим числом известных вам уровней. Полученной дерево приведите к табличной форме. В полях, значения которых неизвестны, поставьте прочерки.

Площадь компании составляет 270 м2. Здание состоит из 7 кабинетов с центральным коридором.

Компьютеры в предприятии расположены вдоль стены. Между собой они соединяются при помощи витой пары, которая вкладывается в кабель-канал, прикрепленный к стене, также подключаются к коммутатору.

В организации имеется 14 рабочих станций, которые объединены в корпоративную сеть.

Под логической структурой сети понимается ее организация на 3-м и выше уровнях модели OSI, т.е. сетевые протоколы, адресация, взаимодействие рабочих станций с серверами. В качестве основного сетевого протокола в вычислительной сети Предприятия используется протокол IP. Адреса на сетевом уровне для рабочих станций задаются динамически по протоколу DHCP.

Рисунок 1 - Логическая схема сети

На данной логической схеме отображена топология расширенная звезда. В схеме показаны необходимые компоненты сети: коммутатор, 14 компьютеров, Web-сервер и сервер.

Теория графов в качестве теоретической дисциплины может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств (бесконечные графы рассматривать мы не будем) с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы. Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Основные понятия теории графов

Граф - система, которая может быть рассмотрена как множество кружков и множество соединяющих их линий. Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок - ребрами.

Рисунок 2 - Пример графа

Способы задания графов:

А) Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2.
Б) Список ребер. В первом столбце ребра, во втором вершины им инцидентные.
В) Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. Dij= число ребер, соединяющее вершины i, j.
Г) Матрица Кирхгофа. bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii = deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

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

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

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

Основные виды графов:

А) Симметричный граф - граф, в котором две смежные вершины соединены противоположно ориентированными дугами.
Б) Ориентированный граф - это граф, на котором указаны стрелки на каждом ребре. Неориентированный граф не имеет стрелок.
В) Полный граф - это когда любые две вершины соединены хотя бы одним ребром.
Г) Сильно связным граф является, когда для любых двух вершин существует путь из одной вершины в другую.
Д) Эйлеровым путем в графе называется путь, содержащий все ребра графа. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.
Е) Гамильтонов путь - путь, содержащий каждую вершину графа ровно один раз.

Рисунок 3 - Эйлеров граф

Нахождение минимального пути по алгоритму Краскала

Алгоритм Краскала - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Краскалом в 1956 году.

Алгоритм нахождения кратчайшего пути:

А) Выбираем ребра наименьшей длины
Б) Из оставшихся ребёр вновь выбираем наименьшей длины
В) Выбираем ребра наименьшей длины при условии, что оно не образует цикла с рёбрами, выбранными в пунктах 1, 2
Г) Из оставшихся рёбер выбираем то, которое меньшей длины и не образовывает цикла с рёбрами, выбранными в пунктах 1-3

Для того, чтобы найти минимальный путь в приведенной выше сети, возьмем для рассмотрения небольшую часть этой сети. Для построения графа возьмем компьютеры под номерами: 1, 2, 3, 4, 5, 6 и Ком 2.

Рисунок 4 - Участок сети №1

В приведенной ниже таблице размещены числовые значения для каждой дуги графа.

Таблица 1 - Числовые значения дуг

Вычислим число ребер в полном графе по формуле:

где m - число ребер, n - число вершин

Для данного графа m = 21

Высчитаем число шагов, за которые мы найдем наименьший путь по следующей формуле:

В данном графе наименьший путь мы найдем за 6 шагов.

Шаг 1: Выберем любой самый короткий путь, например ПК26 ПК27. Числовое значение этой дуги равно 1

Шаг 2: Так же произвольно выбираем еще один путь, учитывая длину. Возьмем ПК29 ПК31 = 1

Шаг 3: Оставшиеся четыре шага мы выбираем кратчайшие пути. При правильном выборе не должны образовываться петли. Берм дугу между ПК25 и ПК26. Она равна 2.

Шаг 4:ПК28 ПК31= 2

Шаг 5: ПК26 ПК31= 3

Шаг 6: ПК29 ПК30 = 3

Считаем общий путь. Для этого необходимо сложить все дуги.

Наименьший путь в данном графе равен 12.

Построение матрицы смежности

Матрица смежности - один из способов представления графа в виде матрицы.

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) - это квадратная матрица Aразмера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали. Матрица смежности и cписки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах.

Свойства матриц смежности:

- если граф симметричен, то его матрица тоже смежности тоже симметрична
- элементами матрицы A(G) являются целые положительные числа и число ноль
- Сумма элементов матрицы A(G) по i-й строке (или по i-му столбцу) равна степени соответствующей вершины d(xi)

- В графе, имеющей матрицу смежности А существует путь длины л, если не равна 0.В графе не существует контуров тогда и только тогда, когда

=0, начиная с некоторого k.

Рассмотрим новый участок сети для построения матрицы смежности.

В граф будут входить следующие элементы сети: коммутатор 1, коммутатор 4, коммутатор 5, 4 ПК под номерами 11, 12, 13, 14.

Рисунок 5 - Участок сети №2

Рисунок 6 - Граф участка сети №2

В данном графе черные дуги обозначают физическое соединение между устройствами, а красные - только логическое.

Для данного графа построим матрицу смежности A = (), где - число дуг, идущих из вершины в вершину .

Проанализировав матицу, можно сделать некоторые выводы:

Графы и их матрицы используются для описания и анализа потоков информации в управляющих системах. В любую управляющую систему поступают исходные данные. В итоге обработки информации от исходных данных получаются промежуточные данные, а из промежуточных данных окончательные результаты.

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

Вершины такого графа - это исходные данные, промежуточные результаты.

Ребра информационного графа указывают на взаимосвязь между этими величинами.

Изобразим участок сети №2, из предыдущего пункта, в виде информационного графа.

Рисунок 7 - Информационный граф

ПК11 - исходные данные

К1 - конечный результат

К5, К4, ПК12, ПК13, ПК14 - промежуточные вершины

Каждый информационный граф содержит вершины каждая, из которых имеет отношение порядка.

Оно разбивает весь процесс движения информации от исходных данных до результатов на такты. Для формирования любой величины необходимо чтобы информация поступала в эту вершину по всем путям вершины от исходных данных.

Порядком вершины Хi называется число равное максимальной из длин путей, ведущих к этой вершине от любого из исходных данных.

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

Так как последний столбец 0, то вершина С - исходные данные. Главная диагональ 0 - граф без петель. Третья строка 0, значит вершина К - конечный результат.

Презентация: «Структура данных». Автор: Фарида Мирзагитовна. Файл: «Структура данных.pptx». Размер zip-архива: 1103 КБ.

Структура данных

Структура данных:

Деревья, сети, графы, таблицы

Разработала учитель информатики МБОУ «СОШ №5 г.Азнакаево» РТ Габдуллина Ф. М.

Граф - отображает элементный состав системы и структуру связей

Описание некоторой местности: «Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.

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

Для сети характерна возможность множества различных путей перемещения

по ребрам между некоторыми парами вершин

Неориентированный граф (сеть)

Для сетей также характерно наличие замкнутых путей, который называются циклами

Как добраться из Р в М ?

Связи между вершинами данного графа несимметричны и поэтому

изображаются направленными линиями со стрелками. Граф с такими свойствами называется ориентированным.

Существует четыре группы крови человека.

При переливании не все группы совместимы. Данный граф показывает возможные варианты переливания крови. Например, из графа видно,что кровь I группы можно переливать любому человеку.

Направленные линии называют дугами (в отличии от ребер неориентированных графов). Линию, выходящую и входящую в одну и ту же вершину называют петлей.

Иерархическая структура

Система административного управления, между элементами которой установлены отношения подчиненности.

Граф иерархической структуры -

Между любыми двумя его вершинами существует единственный путь.

Деревья не содержат циклов и петель

Главная вершина - корень

Листья – не имеют порожденных вершин

Примеры иерархических структур - деревьев

Таблицы

В какой форме представлена информация?

Табличный способ представления данных является универсальным

Кол-во учителей в %

Тренажеры для оттачивания различных навыков

Таблица типа "объект-свойство"

Таблица типа "объект-объект"

Таблица типа «двоичная матрица»

Какая связь между графом и таблицей

Попробуйте представить информацию о дорожной связи между поселками в форме таблицы.

Если сеть является неориентированным графом, то матрица смежности

симметрична относительно главной диагонали.

У матрицы, отражающий ориентированный граф, симметричности не будет

Попробуйте представить информацию о группах крови в форме таблицы.

Зачем мы переводили графы в табличную форму

Вам понятнее граф или таблица? С точки зрения человека, граф гораздо нагляднее и понятнее представляет структуру системы, чем таблица. А компьютеру какую форму обрабатывать легче? Для компьютерной обработки табличная форма подходит лучше. Многие компьютерные технологии (базы данных, электронные таблицы) работают с таблицами и поэтому в компьютерном моделировании чаще работают с табличным представлением.

Подведем итоги

Единственность пути между вершинами

Множественность путей между вершинами

Выполните задания

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

Выполните задания

2. Нарисуйте произвольную структуру глобальной компьютерной сети в виде графа, в котором вершины обозначают серверы, а ребра – линии связи. Опишите эту сеть в виде двоичной матрицы смежности.

Выполните задания

3. Нарисуйте родословное дерево своей семьи (только по мужской линии или только по женской) с наибольшим числом известных вам уровней. Полученной дерево приведите к табличной форме. В полях, значения которых неизвестны, поставьте прочерки.

Читайте также: