их компонент випливає, що в конденсації D * будь-якого орграфа D немає контурів. Очевидно, що конденсація кожного сильного орграфа є тривіальний орграф. Можна показати, що орграф є одностороннім тоді і тільки тоді, коли його конденсація має єдиний остовно шлях.
Орієнтована подвійність і бесконтурние орграфов
Орграф D ', зворотний до даному орграфа D, має ті ж вершини, що і D, a дуга ії належить D 'тоді і тільки тоді, коли дуга ії належить D. Іншими словами, орграф, зворотний до орграфа D, виходить зміною орієнтації кожній дуги орграфа D.
Для будь теореми про орграфа можна сформулювати відповідну двоїсту теорему, замінивши кожне поняття на зворотне до нього. Бесконтурним орграфом називається орграф, що не містить контурів. Бесконтурний орграф містить принаймні одну вершину з нульовою полустепенью результату. Відповідно з позначенням D 'орграфа, зворотного до D, будемо також відзначати штрихами двоїсті результати. Бесконтурний орграф D містить принаймні одну вершину з нульовою полустепенью заходу. Раніше було зазначено, що конденсація будь-якого орграфа є бесконтурний орграф, а наведені вище твердження дають деяку інформацію про бесконтурних орграфа. Дамо тепер кілька характеризації орграфов. Наступні властивості орграфа D еквівалентні: (1) D - бесконтурний орграф, (2) D * ізоморфний D, (3) кожен маршрут орграфа D є шлях; (4) вершини орграфа D можна впорядкувати таким чином, що матриця смежностей "A (D) буде верхньою трикутною матрицею. Особливий інтерес представляють два двоїстих типу бесконтурних орграфов. Джерелом в орграфе! Що виходить дерево *) - • це орграф з джерелом, який не має полуконтуров; вхідне дерево - двоїстий йому орграф. Слабкий орграф є виходять деревом тоді і тільки тоді, коли точно одна його вершина має нульову полустепені заходу, а у всіх інших вершин полустепені заходу дорівнює 1. Слабкий орграф є вхідним деревом тоді і тільки тоді, коли точно одна його вершина має нульову полустепені результату, а у всіх інших вершин полустепені результату дорівнює 1. У функціональному орграфе кожна вершина має полустепені результату, рівну 1; двоїстий до нього орграф називається контрафункціональним орграфом.
Слабкий функціональний орграф
Для слабкого орграфаD наступні твердження еквівалентні: (1) D - функціональний орграф, (2) eD точно один такий контур, що видалення його дуг призводить до орграфа, в якому кожна слабка компонента є вхідним деревом, (3) в D точно один такий контур, що видалення будь-якої його дуги призводить до утворення вхідного дерева. Мінімальний набір вершин, з якого досяжні всі вершини орграфа D, називається вершинної базою орграфа. Кожен бесконтурний орграф має єдину вершинну базу, що складається з усіх вершин з нульовими полустепені заходу. Кожен орграф має вершинну базу, але не кожен має 1-базу. Критерій існування 1-бази у довільного орграфа ще не знайдено. Кожен орграф, що не містить контурів непарної довжини, має 1-базу. Кожен бесконтурний орграф має 1-базу.
Висновок
Теорії графів застосовують у різних галузях науки і техніки:
Інформація: виконавчі дерева грають вельми важливу роль в теорії інформації. Припустимо, що певне число повідомлень потрібне закодувати у вигляді кінцевих послідовностей різної довжини, що складаються з нулів та одиниць. Якщо ймовірності кодових слів задані, то найкращим вважається код, в якому середня довжина слів мінімальна в порівнянні з іншими розподілами ймовірності. Задачу про побудову такого оптимального коду дозволяє вирішити алгоритм Хаффмана. p> Двійкові кодові дерева допускають інтерпретацію в рамках теорії пошуку. Кожній вершині при цьому зіставляється питання, відповісти на який можна або "так", або "Ні". Стверджувальному і негативної відповіді відповідають два ребра, що виходять з вершини. "Опитування" завершується, коли вдається встановити те, що було потрібно.
Таким чином, якщо комусь знадобиться взяти інтерв'ю у різних людей, і відповідь на черговий питання буде залежати від заздалегідь невідомого відповіді на попереднє запитання, то план такого інтерв'ю можна представити у вигляді двійкового дерева.
Хімія. Ще А. Келі розглянув задачу про можливі структурах насичених (або граничних) вуглеводнів, молекули яких задаються формулою: CnH2n +2 ​​
Всі атоми вуглеводню Чотиривалентний, всі атоми водню одновалентних. Молекула кожного граничного вуглеводню являє собою дерево. Якщо видалити всі атоми водню, то решта атоми вуглеводню також будуть утворювати дерево, кожна вершина якого має ступінь не вище 4. Отже, число можливих структур граничних вуглеводнів, тобто число гомологів даного речовини, дорівнює числу дерев з вершинами ступені не більше чотирьох.
Таким чином, підрахунок числа гомологів граничних вуглеводнів також призводить до задачі про перерахування дерев певного типу. Це завдання і її узагальнення розглянув Д. Пойа. p> Елек...
