Контакты 244851268 Телефон 8(067)6446674
Логин: Пароль: Код проверки: captcha >>Забыли пароль?

Поиск

>>Расширенный

Категории

Новости

Вы здесь: Начало > Новости

НОУ ІНТУЇТ | лекція | Початкові поняття теорії графів

  1. Графи і бінарні відносини Нагадаємо, що бінарним відношенням на множині називається будь-яка підмножина...
  2. число графів
  3. Суміжність, инцидентность, ступеня

Графи і бінарні відносини

Нагадаємо, що бінарним відношенням на множині Нагадаємо, що бінарним відношенням на множині   називається будь-яка підмножина   безлічі   , Що складається з різноманітних упорядкованих пар елементів безлічі називається будь-яка підмножина безлічі , Що складається з різноманітних упорядкованих пар елементів безлічі . Кожному такому ставленню можна поставити у відповідність граф відносини . Порівнюючи з тим, що говорилося вище про визначеннях різних типів графів, бачимо, що поняття бінарного відношення еквівалентно поняттю орієнтованого графа з петлями. Інші типи графів без кратних ребер - це приватні види бінарних відносин. ставлення називається рефлексивним, якщо для будь-якого пара належить , І антирефлексивне, якщо жодна така пара не належить . Відношення називається симетричним, якщо з випливає, що . У графі антирефлексивне і симетричного відносини немає петель і для кожної пари вершин або немає жодного, або є два ребра, що з'єднують ці вершини. Якщо в такому графі кожну пару орієнтованих ребер, що з'єднують одні і ті ж дві вершини, замінити одним неорієнтованим ребром, то вийде звичайний граф.

Звідки беруться графи

Легко знайти приклади графів в самих різних областях науки і практики. Мережа доріг, трубопроводів, електричний ланцюг, структурна формула хімічної сполуки, блок-схема програми - в цих випадках графи виникають природно і видно "неозброєним оком". При бажанні графи можна виявити практично де завгодно. Це наочно показано в книзі Д.Кнута [DEKnuth, "The Stanford GraphBase"] - графи витягуються з роману "Анна Кареніна", з картини Леонардо да Вінчі, з матеріалів Бюро Економічного Аналізу США і з інших джерел.

Чимало приводів для появи графів і в самій математиці. Найбільш очевидний приклад - будь багатогранник в тривимірному просторі. Вершини і ребра багатогранника можна розглядати як вершини і ребра графа. При цьому ми відволікаємося від того, як розташовані елементи багатогранника в просторі, залишаючи лише інформацію про те, які вершини з'єднані ребрами. на Мал. 1.4 показані три способи зобразити один і той же граф тривимірного куба.

Ще один спосіб утворення графів з геометричних об'єктів ілюструє Мал. 1.5 . Зліва показано шість кіл на площині, а праворуч - граф, в якому кожна вершина відповідає одному з цих кіл і дві вершини з'єднані ребром в тому і тільки тому випадку, коли відповідні кола перетинаються. Такі графи називають графами перетинань. Можна побудувати граф перетинів сімейства інтервалів на прямій, або дуг окружності, або паралелепіпедів. Взагалі, для будь-якого сімейства множин Ще один спосіб утворення графів з геометричних об'єктів ілюструє   Мал можна побудувати граф перетинів з безліччю вершин , В якому ребро є тоді і тільки тоді, коли і . Відомо, що будь-який граф можна представити як граф перетинів деякого сімейства множин.

число графів

Візьмемо якусь безліч Візьмемо якусь безліч   , Що складається з   елементів, і будемо розглядати всілякі (звичайні , Що складається з елементів, і будемо розглядати всілякі (звичайні!) графи з безліччю вершин . Позначимо число таких графів через . Ці графи розрізняються тільки множинами ребер, а кожне ребро - це невпорядкована пара різних елементів з . В комбінаториці такі пари називаються сполученнями із по 2, їх число дорівнює

Кожна пара може бути включена або не включена в безліч ребер графа. Застосовуючи правило твори, приходимо до наступного результату:

Теорема 1. Теорема 1 .

Суміжність, инцидентность, ступеня

Якщо в графі є ребро Якщо в графі є ребро   , То говорять, що вершини   і   суміжні в цьому графі, ребро   інцидентне кожної з вершин   ,   , А кожна з них инцидентна цьому ребру , То говорять, що вершини і суміжні в цьому графі, ребро інцидентне кожної з вершин , , А кожна з них инцидентна цьому ребру.

Безліч всіх вершин графа, суміжних з даною вершиною Безліч всіх вершин графа, суміжних з даною вершиною   , Називається околицею цієї вершини і позначається через , Називається околицею цієї вершини і позначається через .

На практиці зручним і ефективним при вирішенні багатьох завдань способом завдання графа є так звані списки суміжності. Ці списки можуть бути реалізовані різними способами у вигляді конкретних структур даних, але в будь-якому випадку мова йде про те, що для кожної вершини На практиці зручним і ефективним при вирішенні багатьох завдань способом завдання графа є так звані списки суміжності перераховуються всі суміжні з нею вершини, тобто елементи безлічі . Такий спосіб завдання дає можливість швидкого перегляду околі вершини.

Число вершин, суміжних з вершиною Число вершин, суміжних з вершиною   , Називається ступенем вершини   і позначається через , Називається ступенем вершини і позначається через .

Якщо скласти ступеня всіх вершин деякого графа, то кожне ребро внесе в цю суму внесок, рівний 2, тому справедливо наступне твердження:

Теорема 2. Теорема 2 .

Це рівність відомо як "лема про рукостискання". З нього випливає, що число вершин непарного ступеня в будь-якому графі парне.

вершину ступеня вершину ступеня   називають ізольованою називають ізольованою.

Граф називають регулярним ступеня Граф називають регулярним ступеня   , Якщо ступінь кожної його вершини дорівнює , Якщо ступінь кожної його вершини дорівнює .

Набір ступенів графа - це послідовність ступенів його вершин, виписаних в неубутних порядку.