Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Тема 7. 2 теорема о сумме степеней вершин графа. Полный граф, его свойства.
Граф Г называется полным, если каждые две его вершины соединены одним и только одним ребром. А В
С Д - не полный граф
А В
С Д - полный граф
Только для неориентированного графа существует дополнение: Г
– дополнение
Дополнением графа Г называется новый граф , состоящий из всех тех же вершин, что и граф Г и тех и только тех ребер, которые надо добавить, чтобы граф Г стал полным.
В Д Е А С
Степень А=1, степень В=2, степень С=2, степень Д=1, степень Е=0 Степень каждой вершины полного графа на единицу меньше числа вершин. Теорема: Сумма степеней всех вершин графа есть число четное и равное удвоенному количеству ребер
При большом количестве вершин схема теряет свою наглядность и поэтому используют другой способ задания графов в виде матрицы смежностей. где каждое
М – симметричная на главной диагонали – 0 М(Г)=
Лабораторная работа № 2.
Задание графа матрицей смежности Цель работы: 1) Изучить понятия полный граф, дополнение графа. 2) Рассмотреть способ задания графа с помощью матрицы смежности. Литература: 1) "'Графы и их применение". Березина Л.Ю.. М: Просвещение. 1979г. 2) "Теория графов. Алгоритмический подход", Кристофидес Н. 3) "Применение теории графов в программировании". Евстигнеев В.А. - М.: Наука. 1985г. Порядок выполнения работы: I Разработать схему алгоритмов основной программы и подпрограмм. II Написать и отладить программу на языке Turbo Pascal. Задача
Граф задан матрицей смежности М= Изобразить граф, исходя из внешнего вида данной матрицы. Краткие теоретические сведения: Матричный эквивалент графа широко используется в работе с графами на ЭВМ. Граф называется полным, если каждые две его вершины соединены одним и только одним ребром. -полный граф
Граф, не являющийся полным, можно преобразовать в полный граф с теми же вершинами, добавив недостающие ребра. Вершины графа Г и ребра, которые добавлены, также образуют граф, такой граф называется дополнением и обозначается . Каждой вершине графа можно поставить в соответствие строку и столбец с номером i, причем
{ 1, если { 0, если
Тогда матрица называется матрицей смежностей графа Г и обозначается М(Г). Содержание отчета: 1) Составление алгоритмов. 2) Написание программы на языке Turbo Pascal 3) Отладка программы. Контрольные вопросы: 1) Что такое полный граф? 2) Дайте понятие дополнение графа? 3) Что такое матрица смежностей графа? 4) Как составить матрицу смежностей?
|
|||||||||||
Последнее изменение этой страницы: 2017-02-17; просмотров: 196; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.133.147.252 (0.005 с.) |