Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Математика Математика

Матрицы графов

Ночник-проектор "Звездное небо и планеты", фиолетовый.
Оригинальный светильник - ночник - проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фонариков) 2) Три
330 руб
Раздел: Ночники
Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее
Совок №5.
Длина совка: 22 см. Цвет в ассортименте, без возможности выбора.
18 руб
Раздел: Совки

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра информатики РЕФЕРАТ На тему: «Матрицы графов» МИНСК, 2008 В теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов. Матричная форма задания графов обладает достаточной наглядностью при любой степени сложности графа и, что самое важное, позволяет автоматизировать процесс обработки информации, представленной в терминах теории графов, – любая матрица графа может быть введена в ЭВМ. При задании графов в матричной форме могут учитываться либо отношения смежностей (вершин или ребер (дуг)), либо отображения инцидентности (вершин и ребер (дуг)). В связи с этим матрицы графов делятся на два основных класса: матрицы смежностей и матрицы инциденций. Определение.1. Матрицей смежности вершин неориентированного графа G называется квадратная матрица A(G)= порядка p=p(G) (p – количество вершин графа), элементы aij которой равны числу ребер, соединяющих вершины xi и xj. x1 x2 x3 x4 x5 x6 x7 x8 x1 2 0 0 0 1 0 1 0 x2 0 0 1 0 0 1 1 0 x3 0 1 0 1 0 1 0 0 A(G) = x4 0 0 1 0 1 0 0 0 x5 1 0 0 1 0 0 0 1 x6 0 1 1 0 0 0 0 0 x7 1 1 0 0 0 0 0 0 x8 0 0 0 0 1 0 0 0 На рис. 1 приведен неориентированный граф G(X, E) и справа – соответствующая ему матрица смежностей вершин A(G). Из определения 1 непосредственно вытекают основные свойства матриц этого вида. 1. Матрица смежностей вершин неориентированного графа A(G) является квадратной и симметричной относительно главной диагонали. 2. Элементами матрицы A(G) являются целые положительные числа и число ноль. 3. Сумма элементов матрицы A(G) по i-й строке (или по i-му столбцу) равна степени соответствующей вершины d(xi). Из определения матрицы смежностей вершин неориентированного графа и ее основных свойств следуют некоторые особенности соответствия между графом G(X, E) и его матрицей A(G). На рис. 1 указана некоторая нумерация вершин графа; расположенная рядом матрица соответствует именно этой нумерации. Если же в графе G(X, E), приведенном на этом рисунке, использовать другую нумерацию вершин (например, сдвинув ее относительно вершин по часовой стрелке), то это приведет к тому, что в матрице A(G) произойдет перестановка отдельных строк и столбцов. Поэтому говорят, что каждый неориентированный граф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная симметричная относительно главной диагонали матрица, элементами которой являются целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма неориентированный граф, матрицей смежностей вершин которого является данная матрица. Рекомендуется самостоятельно построить матрицу смежностей вершин графа G(X, E), показанного на рис. 1, с использованием другой нумерации вершин и сравнить полученную при этом матрицу с матрицей смежностей вершин приведенного графа. Определение 2. Матрицей смежности вершин ориентированного графа G называется квадратная матрица A(G)= порядка ( – число вершин графа), элементы которой aij равны числу дуг, исходящих из вершины xi и заходящих в вершину xj.

x1 x2 x3 x4 x5 x6 x7 x8 x1 0 0 0 0 0 0 0 0 x2 0 0 0 0 0 1 0 0 x3 0 1 0 0 1 0 1 0 A(G) = x4 1 0 0 0 0 0 0 0 x5 0 0 0 0 1 1 0 0 x6 0 0 0 0 0 0 0 1 x7 0 0 0 0 0 1 0 0 x8 1 0 0 0 1 0 0 0 На рис. 2 показан ориентированный граф G(X, E) и справа – матрица смежностей его вершин. Из определения следует, что сумма элементов i-й строки матрицы A(G) орграфа равна полустепени исхода d (xi), а по i-му столбцу – полустепени захода d-(xi). По-прежнему элементы этой матрицы – целые положительные числа и число ноль. Матрица смежностей вершин орграфа может оказаться симметричной относительно главной диагонали лишь в редких частных случаях. Как и в случае неориентированных графов, каждый орграф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная матрица, элементы которой – целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма ориентированный граф. Определение 3. Матрицей инцидентности неориентированного графа G называется матрица B(G)= размером (p x q) (p и q – количество вершин и ребер графа), элементы bij которой равны единице, если вершина xi инцидентна ребру ej и нулю, если соответствующие вершины и ребра не инцидентны. Свойства матрицы инцидентности неориентированного графа. 1. Сумма элементов матрицы на i-й строке равна d(xi). 2. Сумма элементов матрицы по i-му столбцы равна 2. Матрица инцидентности графа, изображенного на рис. 1, а имеет вид: e1 E2 e3 e4 e5 e6 e7 e8 e9 e10 x1 1 1 2 0 0 0 0 0 0 0 x2 0 0 0 1 1 1 0 0 0 0 x3 0 0 0 0 0 1 1 1 0 0 B(G) = x4 0 0 0 0 0 0 0 1 1 0 x5 1 0 0 0 0 0 0 0 1 1 x6 0 0 0 0 1 0 1 0 0 0 x7 0 1 0 1 0 0 0 0 0 0 x8 0 0 0 0 0 0 0 0 0 1 Следует отметить, что петле ej=(xi, xi) в матрицах этого вида соответствует j-й столбец, состоящий из нулей и одной единицы, расположенной на i-м месте. Ребру ek={xm, x } соответствует в матрице инциденций k-й столбец, состоящий из нулей и двух единиц, расположенных на m-м и -м местах. Нулевая строка матрицы соответствует изолированной вершине, а нулевой столбец – петле. Следует иметь ввиду, что нулевой столбец матрицы инцидентности лишь указывает на наличие петли, но не содержит информации о том, с какой именно вершиной связана эта петля. Необходимо отметить, что между строками матрицы инцидентности B(G) существует очевидная зависимость. Так как каждый столбец этой матрицы содержит только два единичных элемента или состоит только из нулей, если столбец соответствует петле, то сумма по модулю 2 всех строк равна нулю. Поэтому без потери информации о графе вместо матрицы B(G) можно рассматривать сокращенную матрицу Bo(G), получаемую из B(G) вычеркиванием любой строки (чаще всего вычеркивается последняя строка). Таким образом, из p строк матрицы B(G) связного графа (см. п. 5) одна строка всегда линейно зависима, т.е. ранг матрицы B(G) не может превышать p-1 (ранг матрицы B(G) в точности равен p-1). Любое подмножество столбцов матрицы B(G) можно рассматривать как матрицу инцидентности Bґ(G) некоторого суграфа Gґ(X, Eґ), содержащего все вершины исходного графа и соответствующее выделенным столбцам подмножество EґCE его ребер.

Все столбцы матрицы Bґ(G) линейно независимы тогда и только тогда, когда суграф Gґ(X, Eґ) не содержит циклов. Действительно, если совокупность ребер образует цикл, то каждая вершина инцидента четному числу ребер этого цикла. Следовательно, сумма по модулю 2 соответствующих столбцов дает нулевой столбец, что означает из зависимость. Если же суграф не содержит циклов, то он имеет по меньшей мере две (вообще, четное число) концевых вершин, каждая из которых инцидентна только одному ребру, являющемуся концевым. Поэтому сумма по модулю 2 соответствующих столбцов будет содержать два (или четное число) единичных элемента и, следовательно, совокупность этих столбцов независима. В связном графе с p вершинами всегда можно выделить p-1 ребер так, чтобы они образовали суграф без циклов, представляющий собой дерево графа, являющееся каркасом. Поэтому матрица инцидентности содержит не менее p-1 независимых столбцов. В то же время любой суграф, имеющий более p-1 ребер, обязательно содержит цикл, т.е. в матрице инциденций не может быть больше p-1 независимых столбцов. Отсюда следует, что матрица инцидентности связного графа содержит в точности p-1 независимых столбцов, и поэтому ее ранг равен p-1. Число =p-1 и определяет ранг графа. Определение 4. Матрицей инцидентности орграфа G с p вершинами и q ребрами называется матрица B(G) = размером (p ґ q), элементы которой определяются следующим образом: м1, если вершина xi является началом дуги ej bij =н-1, если вершина xi является концом дуги ej; 0, если вершина xi не инцидентна дугу ej . Ниже приведена матрица инцидентности графа, изображенного на рис. 2: e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 x1 0 0 0 0 -1 0 0 0 0 0 -1 x2 1 -1 0 0 0 0 0 0 0 0 0 x3 0 1 1 1 0 0 0 0 0 0 0 B(G) = x4 0 0 0 0 1 0 0 0 0 0 0 x5 0 0 0 -1 0 ±1 1 0 0 -1 0 x6 -1 0 0 0 0 0 -1 1 -1 0 0 x7 0 0 -1 0 0 0 0 0 1 0 0 x8 0 0 0 0 0 0 0 -1 0 1 1 Матрица инцидентности орграфа G обладает следующими свойствами. Сумма строк матрицы B(G) является нулевой строкой. Любая строка матрицы B(G) является линейной комбинацией остальных строк. Ранг матрицы B(G) равен p-1. Определение 5. Матрицей смежности ребер неориентированного графа G называется квадратная матрица A (G) = порядка q, элементы a ij которой равны единице, если ребра ei и ej смежны, и нулю – в противном случае. Для графа, изображенного на рис. 1, матрица смежности ребер имеет вид e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e1 0 1 1 0 0 0 0 0 1 1 e2 1 0 1 1 0 0 0 0 0 0 e3 1 1 2 0 0 0 0 0 0 0 e4 0 1 0 0 1 1 0 0 0 0 e5 0 0 0 1 0 1 1 0 0 0 A (G) = e6 0 0 0 1 1 0 1 1 0 0 e7 0 0 0 0 1 1 0 1 0 0 e8 0 0 0 0 0 1 1 0 1 0 e9 1 0 0 0 0 0 0 1 0 1 e10 1 0 0 0 0 0 0 0 1 0 Очевидно, что матрица A (G) смежности ребер неориентированного графа обладает теми же свойствами, что и матрица A(G) смежности вершин графа G. Таким образом, можно найти граф G , матрица смежности вершин которого равна матрице A (G) смежности ребер графа G. G(X,E) ® A (G) є A(G ) ® G . Такой граф называется реберным, или сопряженным графом G. На рис. 3 приведен реберный граф (для неориентированного графа, показанного на рис.1). Матрицы смежности вершин и смежности ребер неориентированного графа могут быть получены из матрицы инцидентности следующим образом.

Описать модели бизнес-процессов заказчика, существующих как есть. 1.2. Проанализировать разработанные модели бизнес-процессов и функций как есть и сформулировать рекомендации по повышению их эффективности. 1.3. Сформулировать модели бизнес-процессов и функций как должно быть. 1.4. Спроектировать базовый план в формате BBS (формат даст методист Дунько) по внедрению моделей бизнес-процессов. Слушая первые четыре пункта, Безбашнев удовлетворенно кивал, только под конец заметил: PВот здесь, в этом пункте, надо добавить: и качественного распределения всех функций и задач между подразделениями, руководителями подразделений и сторонними организациями, привлекаемыми на договорной основе. PХорошо, идем дальше. Матрица работ с предметом исследования PВас устраивает наполнение?P коротко спросила Пионероге-роева, разворачивая таблицу. PНу, я посмотрю!P Безбашнев махнул рукой и принялся сгребать бумаги со стола. PЭто не все. Босс перестал кивать и больше не испытывал удовлетворения от происходящего. Примерно со второй графы матрицы исследований его внимание переключилось на пылинку, приставшую к свистульке Рыцарь на коне, стоявшей на его столе

1. Графы. решение практических задач с использованием графов (С++)

2. Соединение двух компьютеров в локальную сеть

3. Граф А. А. Аракчеев. Современный взгляд на личность на основе анализа и сравнительной характеристики исторических источников и литературы

4. Оптимальное управление вычислениями в распределенных вычислительных системах на основе графа потоков данных

5. Работа с графами

6. Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем
7. Теория графов и её применение
8. Задача остовных деревьев в k–связном графе

9. Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика»

10. Алмаз-графит

11. Невольник чести (о графе Михаиле Воронцове)

12. Графы

13. Теория графов

14. Обучение решению математических задач с помощью графов

15. Аллотропные видоизменения углерода: графит и алмаз

16. Математическое моделирование высокочастотных радиоцепей на основе направленный графов

Ручка шариковая "Excellence", розовая.
Новая подарочная шариковая ручка имеет необычный дизайн, который притягивает взгляд. Металлический миниатюрный корпус полностью усыпан
444 руб
Раздел: Металлические ручки
Машина-каталка "Лидер", цвет: бордовый.
Игрушечный автомобиль снабжен рулем, фарами, зеркалами заднего вида и звуковыми модулями, а его корпус оформлен в приятном бордовом цвете.
2947 руб
Раздел: Каталки
Игрушка-плита со звуком и подсветкой"Miele".
Все как у мамы! Точная игрушечная копия фирменной плиты MIELE. Игрушка функциональная: конфорки и духовка светятся, издает реалистичные
1680 руб
Раздел: Плиты

17. Граф Алексей Андреевич Аракчеев

18. Реакторный графит: разработка, производство и свойства

19. Графічний планшет Wacom Graphire

20. Модели теории графов для выделения контуров по градиентному изображению

21. Поиск в ширину на графах

22. Модификация алгоритма определения клик графа с параметрической адаптацией
23. Антуан Гамильтон. Мемуары графа де Грамона
24. Граф Л.Н. Толстой: путь к «Войне и миру»

25. Юмор и сатира в поэзии графа А.К. Толстого

26. Поиск клик в графах

27. Способи і заходи захисту від шуму в поліграфії

28. Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления

29. Алгоритмы на графах. Независимые и доминирующие множества

30. Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему

31. Види компютерної графіки

32. Вирізання картинок з екрану та запис їх в BMP форматі (для графіки) і TXT форматі (для тексту)

Настольная игра "Кортекс".
Сможете отличить баскетбольный мяч от клубники на ощупь или за долю секунды увидеть выход из лабиринта? А молниеносно запомнить предметы и
914 руб
Раздел: Карточные игры
Книга-сейф "Английский словарь", цвет: черный, 24 см.
Этот сейф-шкатулка - точная имитация книги. Будучи поставленным на книжную полку, он ловко затеряется среди настоящей литературы, сохранив
711 руб
Раздел: Копилки
Карандаши для левшей "EasyColors", 12 цветов.
Эти эргономичные цветные карандаши позволяют подготовить руку к письму и сформировать навык работы с пишущими инструментами. Специальные
1517 руб
Раздел: 7-12 цветов

33. Комп’ютерна графіка

34. Определение связности графа на Лиспе

35. Отримання зображень з допомогою комп’ютерної графіки

36. Побудова ліній та точок з допомогою комп’ютерної графіки

37. Поліграфічний синтез кольорових зображень

38. Розпорядчі документи можливості роботи з текстом в графічному редакторі corel draw
39. Гамильтоновы графы и сложность отыскания гамильтоновых циклов
40. Загальні системи комп’ютерної графіки

41. Графічне та геометричне моделювання та інтерактивні системи

42. Графічний інтерфейс користувача Linux

43. Динамическое программирование, алгоритмы на графах

44. Политический деятель граф Потемкин-Таврический

45. Музей Усольской усадьбы графов Орловых-Давыдовых

46. Алгоритм раскраски графа (точный)

47. Графы и частично упорядоченные множества

48. Деревья и их свойства (частный вид графов)

Игрушка-плита со звуком и подсветкой"Miele".
Все как у мамы! Точная игрушечная копия фирменной плиты MIELE. Игрушка функциональная: конфорки и духовка светятся, издает реалистичные
1680 руб
Раздел: Плиты
Брошюровщик "Heidi Swapp. The Cinch".
Брошюровщик делает квадратные отверстия и предназначен для создания календарей, блокнотов, альбомом и много другого в домашних условиях.
8099 руб
Раздел: Прочее
Принцессы. 5 часов активной игры. Более 400 наклеек!. Ватт Фиона
Все девчонки очень любят наряжаться! А еще они с удовольствием поют и танцуют. Им нравится путешествовать, узнавать что-то новое и вообще
346 руб
Раздел: Альбомы, коллекции наклеек

49. Книга як поліграфічне видання

50. Аналіз педагогічного досвіду формування графічних умінь у молодших школярів на уроках трудового навчання

51. Методика формування навичок зображення форми у процесі графічної діяльності молодших школярів

52. Реалізація шляхів естетичного виховання першокласників у процесі формування каліграфічної навички

53. Шляхи формування навичок каліграфічного письма

54. Логический анализ E-структур с помощью графов
55. Дисперсійний аналіз та побудова статистичних графіків
56. Прикладной системный анализ: сетевой анализ и календарное планирование проектов, метод прогнозного графа

57. Соединенные Штаты Америки

58. Важнейшие природные соединения алюминия

59. Правительство Соединенных Штатов

60. Особенности изображения двух миров в поэме А. Блока "Двенадцать"

61. История литературы Соединенных Штатов Америки

62. Немецкий менталитет и происхождение двух мировых войн (Райнер Бендик)

63. Методы компьютерной обработки статистических данных. Проверка однородности двух выборок

64. Программирование ориентированное на объекты

Стиральный порошок KAO "Attack Bio EX", 1 кг.
Стиральный био-порошок KAO "Attack Bio EX" признан Международным Авторитетным Советом США по хлопку в качестве выдающегося
620 руб
Раздел: Стиральные порошки
Шкатулка "Мишка", 7x10 см.
Шкатулка сохранит ваши ювелирные изделия в первозданном виде. С ней вы сможете внести в интерьер частичку элегантности. Регулярно удалять
332 руб
Раздел: Шкатулки сувенирные
Рюкзачок "Снеговик".
Симпатичный детский рюкзачок сшит из мягкой ткани ярких расцветок и украшен изображением снеговика. Во внутреннее отделение поместятся
706 руб
Раздел: Детские

65. Объектно-ориентированные СУБД

66. Сравнительный анализ каскадной и спиральной моделей разработки программного обеспечения

67. Изучение статистической зависимости двух случайных величин на примере массы и диаметра луковицы гладиолуса

68. Патогенез язвенной болезни и желчнокаменной болезни как двух вариантов одного психосоматического заболевания

69. Личностно-ориентированное развивающее обучение И.С. Якиманской

70. Важнейшие природы соединения алюминия
71. MIG MAG TIG сварка, установка ванн и душевых поддонов, соединение пластмассовых труб
72. Уплотнение неподвижных соединений

73. Контроль качества сварных соединений

74. Проблемно-ориентированное консультирование

75. Трехфазный ток, переходной процесс, четырехполюсник

76. Устойство измерения отношения двух напряжений

77. Получение и применение кальция и его соединений

78. Межпредметные связи в курсе школьного предмета химии на предмете углерода и его соединений

79. Фосфор и его соединения

80. Углерод и его соединенния

Набор посуды керамической "Миньоны" (3 предмета), желтый.
Набор детской керамической посуды с изображением героев любимых диснеевских мультфильмов в подарочной упаковке. Состав набора: • тарелка:
547 руб
Раздел: Наборы для кормления
Пивная кружка "Пиво утром, как известно, не так вредно, как полезно", 500 мл, 14 см.
Состав: керамика, ПМ. Мыть тёплой водой с применением нейтральных моющих средств.
720 руб
Раздел: Кружки
Средство для купания Bubchen, 400 мл.
Мягкое средство для купания младенцев c лекарственными травами стабилизирует кислотно-щелочной баланс кожи и поддерживает ее естественную
413 руб
Раздел: Экстракты, сборы

81. Исследование свойств хрома и его соединений

82. Структура и функции Банка Англии /Центрального Банка Соединенного Королевства/

83. Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления

84. Раздел Германии и образование двух немецких государств

85. Меж двух зол

86. Повесть о том, как один мужик двух генералов прокормил. Салтыков-Щедрин М.Е.
87. Анализ композиционных особенностей древнеегипетских фресок на примере двух-трёх памятников разных периодов
88. Актуальность и правда жизни на страницах «Повести о том, как один мужик двух генералов прокормил» М. Е. Салтыкова-Щедрина

89. Теория Родиона Раскольникова о "двух разрядах людей" и ее опровержение

90. Особенности изображения двух миров в поэме А.Блока «Двенадцать»

91. О символистских источниках двух стихотворений Алексея Кручёных

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

93. Практика проведения иммунизации педиатрами и семейными врачами в Соединенных Штатах

94. Соединения костей верхней конечности

95. Барий и его соединения

96. Схемы соединения гальванических элементов. Схема включения реостата. Схема включения потенциометра

Точилка "Божья коровка", электрическая с контейнером (2 запасных лезвия EG-5009).
Электрические точилки помогут быстро, качественно и без каких-либо усилий заточить карандаши. А яркие и необычные дизайны порадуют детей и
451 руб
Раздел: Точилки
Макси-пазлы "Ягоды", 20 элементов.
Макси-пазлы разработаны специально для маленьких детей. Крупные крепкие детали удобны для захвата детской ручкой. А красочное оформление
426 руб
Раздел: Пазлы (Maxi)
Рюкзак "Basic. Чемпионат мира по футболу 2018", 30х41х13 см.
1 большое отделение с 1 внутренним отделением. 1 накладной карман спереди. Удобные лямки, позволяющие регулировать длину. Размер 30х41х13
1150 руб
Раздел: Канцтовары, хобби

97. Изучение соединения резисторов

98. Расчет болтовых соединений и штифтов

99. Реализация личностно-ориентированного подхода на уроках английского языка


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.