ЗМІСТ
ВСТУП
РОЗДІЛ 1. ПОНЯТТЯ СПЕКТРА ГРАФА
.1 ПОНЯТТЯ СПЕКТРА ГРАФА
.2 ОСНОВНІ ПОНЯТТЯ І ПОЗНАЧЕННЯ
.3НЕКОТОРИЕ ТЕОРЕМИ ТЕОРІЇ МАТРИЦЬ ТА ЇХ ЗАСТОСУВАННЯ ДО ДОСЛІДЖЕННЯ СПЕКТРІВ ГРАФІВ
РОЗДІЛ 2. ЗВ'ЯЗКУ МІЖ спектрального ВЛАСТИВОСТЯМИ ГРАФІВ
.1 орграфа
.2 ГРАФИ
.3 регулярний граф
РОЗДІЛ 3. ПРЕДФРАКТАЛЬНИЙ ГРАФ з запалом регулярної СТУПЕНЯ
.1 ВИЗНАЧЕННЯ ПРЕДФРАКТАЛЬНОГО І фрактальної ГРАФА
.2 СПЕКТР ПРЕДФРАКТАЛЬНОГО ГРАФА з запалом регулярної СТУПЕНЯ.
ВИСНОВКИ
СПИСОК ЛІТЕРАТУРИ
ВСТУП
В останні десятиліття значно зросла наукова активність в області дискретної математики, яка переживає період інтенсивного розвитку і проникнення в найрізноманітніші галузі знання. Найбільш яскраво це проявилося в одному з її розділів - теорії графів, обширні можливості додатку якого обумовлені теоретико-множинними, комбінаторними і топологічними аспектами, складовими основу поняття самого графа. Успіх застосування методів теорії графів можна пояснити також тим, що вона являє собою зручний мову для формулювання завдань, що відносяться до вельми широкому колу наукових проблем, і є ефективним інструментом для їх вирішення.
У теорії графів розвинені спеціальні методи для вирішення різних завдань, але ще мало спільних методів, що дозволяють одноманітно вирішувати цілі класи завдань. В якості джерел створення таких досить загальних методів найчастіше виступають інші раніше сформовані галузі математики. Прикладом може служити лінійна алгебра, в результаті застосування якої в теорії графів виник новий напрям - спектральна теорія графів, заснована на алгебраїчних инвариантах графа - його спектрах. Хоча розвиваються у цієї теорії методи і не можуть дати звіт на всі питання, пов'язані з конкретною характеризацією графа, проте вони дозволяють отримати кращі результати в порівнянні з іншими існуючими методами.
Наведено додатки спектральних методів в теорії графів, комбінаторики, хімії та фізики, описані хімічні та фізичні моделі, в яких спектри графів мають важливе самостійне значення.
Останнім часом теоретико-графові (топологічні) підходи придбали для хімії велике значення, що, на думку фахівців, обумовлено декількома причинами: по-перше, результати, отримані при топологічному розгляді, не завжди можуть бути вилучені з прямих чисельних розрахунків; по-друге, існує багато молекулярних властивостей, які найкраще піддаються поясненню за допомогою уявлень, заснованих на понятті зв'язності молекулярного гpaфa. Підвищений інтерес, що проявляється до теорії графів, викликаний також тим, що теорія молекулярних орбіталей Хюккеля продовжує удосконалюватися і успішно застосовуватися в хімії сполучених молекул. Аналіз теорії Хюккеля мовою теорії графів не тільки відкриває нові можливості для наочної інтерпретації, але і дозволяє глибше розібратися в структурному обгрунтуванні численних закономірностей, встановлених для p -Електронна систем.
РОЗДІЛ 1. ПОНЯТТЯ СПЕКТРА ГРАФА
. 1 ПОНЯТТЯ СПЕКТРА ГРАФА
Спектр графа - це множина всіх власних значень матриці суміжності з урахуванням кратних ребер.
Кратні ребра - кілька ребер, інцидентних одній і тій же вершині.
Граф включає безліч вершин і безліч ребер, що є підмножиною декартова квадрата безлічі вершин (тобто кожне ребро з'єднує рівно дві вершини).
Орграф G=(V, E) є пара множин, V- безліч вершин, Е- безліч дуг.
Дуга - це впорядкована пара вершин (V, W), де вершину V називають початком, а W- кінцем дуги.
Графи з неорієнтованими або орієнтованими кратними ребрами називаються відповідно мультиграфом або мультіорграфамі. У цих випадках допускається існування петель (петля - це ребро або дуга, обидві вершини якої збігаються). Використовувана термінологія збігається з термінологією Харарі, з тією лише відмінністю, що в цій роботі мультиграфом (мультіорграфах) допускається наявність петель. Хоча терміном «граф» прийнято позначати те, що в деяких роботах по теорії графів називається «кінцевим неорієнтованим графом без петель і кратних ребер» (або, коротше, «звичайним графом»), ми заради зручності читання будемо іноді (коли це не викличе непорозумінь ) використовувати термін «граф» в більш широкому сенсі, т. е. будемо цим терміном позначати неорієнтовані графи, орграф і навіть мультиграфом і мультіорграфи.
Дві вершини називаються суміжні, якщо вони з'єднані ребром (дугою). Матриця суміжності А мультиграфом (мультіорграфа) G з безліччю вершин {х1, х2,, хn} - це квадратна матриця порядку n, в якій значення aij елемента, розташованого на місці (i, j) дорівнює ...
