Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E — підмножина V × V.
Визначення графа є настільки загальним, що цим терміном можна описувати безліч подій та об'єктів повсякденного життя. Високий рівень абстракції та узагальнення дозволяє використовувати типові алгоритми теорії графів для вирішення зовнішньо несхожих задач у транспортних і комп'ютерних мережах, будівельному проектуванні, молекулярному моделюванні тощо. Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або запроектовані будинки, споруди, квартали тощо розглядаються як вершини, а дороги, інженерні мережі, лінії електропередачі, що їй з'єднують, тощо — як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.
Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.
Нехай X = { x1,…,xn} — деяка скінченна множина (множина вершин), M2 — множина всіх невпорядкованих пар елементів з X,
1. Граф G(V, E) — пара множин V, E ⊂ M2. Множина V — це множина вершин, множина E — це множина ребер. Якщо (xi,xj) ∈ E, то ми говоримо, що ребро (xi,xj) сполучає вершину xi з вершиною xj; інша термінологія — ребро (xi,xj) і вершини xi та xj інцидентні.
2. Граф G(V, E) називається повним, якщо E = M2.
Якщо множина V містить n вершин, то, очевидно, число ребер повного графа дорівнює Cn2. Повний граф з n вершинами позначається Kn.
3. Граф G(V, E) називається порожнім, якщо V = ∅.
4. Вершини xi та xj графа G(V, E) інцидентні, якщо (xi,xj) ∈ E.
5. Степенем d(xi) вершини xi графа G(V, E) називається число вершин xj, які інцидентні вершині xi (число відрізків, які виходять з вершини xi).
6. Якщо d(xi)=1, то вершина xi називається кінцевою вершиною графа G(V, E). Якщо d(xi)=0, то вершина xi називається ізольованою.
7. Шляхом називається скінченна послідовність вершин, у якій будь-які дві сусідні вершини сполучені ребром.
8. Циклом є шлях, в якому перша і остання вершини збігаються. Наприклад, через S 1 {\displaystyle S^{1}} позначається граф, гомеоморфний циклу (1-поліедр, тобто клас еквівалентності декотрого графа за відношенням гомеоморфності). Одновимірні поліедри є ломаними лініями (причому припускається їх розпадання на шматки, а також галуження: у одній вершині можуть змикатися скільки завгодно відрізків). Іншими словами, у топологічному сенсі граф представляє собою CW-комплекс розмірності 1 (ребра такого графа представляють відкриті підможини, гомеоморфні одиничному інтервалу (див. Шлях (топологія))).
9. Гомологічний цикл у графі — набір його ребер, для якого з кожної вершини виходить парне число ребер набору. Вживають також термін «замкнена крива» у графі. Наприклад, об'єднання ребер прямокутників, на які робивається пляшка Клейна на один багатокутник, є вісьміркою, тому у цьому графі є чотири цикли. Цикли у G {\displaystyle G} утворюють групу із рангом, який є цикломатичним числом, λ λ --> ( G ) = | E ( G ) | − − --> | V ( G ) | + v , {\displaystyle \lambda (G)=|E(G)|-|V(G)|+v,} де v {\displaystyle v} чисельність компонент зв'язності графа G {\displaystyle G} .
10. Група H 1 ( G ) {\displaystyle H_{1}(G)} усіх циклів у графі G {\displaystyle G} із операцією суми по модулю 2 називається групою гомологій графа G {\displaystyle G} (одновимірною із коефіцієнтами Z 2 {\displaystyle \mathbb {Z} _{2}} ). Наприклад, H 1 ( G ) ≅ ≅ --> Z 2 E − − --> V + 1 {\displaystyle H_{1}(G)\cong \mathbb {Z} _{2}^{E-V+1}} для зв'язного графа G {\displaystyle G} із V {\displaystyle V} вершинами та E {\displaystyle E} ребрами. Це слідує з того, що сума будь-якого елемента із собою дорівнює нулю, однак це є невірним для | H 1 ( G ) | = 2 E − − --> V + 1 . {\displaystyle |H_{1}(G)|=2^{E-V+1}.}
11. Граф є зв'язним, якщо будь-які його вершини можна сполучити шляхом. Кількості вершин, ребер та компонент зв'язності позначаються V , E , C {\displaystyle V,E,C} відповідно.
12. Граф G {\displaystyle G} є підграфом графа H , {\displaystyle H,} якщо кожна вершина графа G {\displaystyle G} є вершиною графа H , {\displaystyle H,} і кожне ребро графа G {\displaystyle G} є ребром графа H . {\displaystyle H.} При цьому дві вершини G {\displaystyle G} , сполучені ребром у H , {\displaystyle H,} не обов'язково сполучені ребром у G {\displaystyle G} .
13. Графи G 1 {\displaystyle G_{1}} та G 2 {\displaystyle G_{2}} є ізоморфними, якщо існує бієкція f {\displaystyle f} множини V 1 {\displaystyle V_{1}} вершини графа G 1 {\displaystyle G_{1}} на множину V 2 {\displaystyle V_{2}} вершин графа G 2 {\displaystyle G_{2}} , яке задовільняє умові: вершини A , B ∈ ∈ --> V 1 {\displaystyle A,B\in V_{1}} є сполученими ребром лише у тому випадку, якщо вершини f ( A ) , f ( B ) ∈ ∈ --> V 2 {\displaystyle f(A),\,f(B)\in V_{2}} сполучені ребром. Задача перевірки ізоморфізму графів належить до класу задач, для яких поки що невідомо, чи є вони поліноміально вирішуваними, чи ні. Тобто поки що не побудований поліноміальний алгоритм перевірки ізоморфізму графів. Ізоморфізм можна розглядати також як перенумерацію вершин графа, тому будь-яка кількісна характеристика структури графа залишається незмінною. Такі характеристики називаються інваріантами графа[1].
14. Два графи є гомеоморфними, якщо від одного можна перейти до іншого за допомогою операцій підрозділення ребра й зворотних до них. Це є еквівалентним існуванню графа, який можна отримати з даних графів операціями підрозділення ребра. Одновимірні групи гомологій гомеоморфних графів є ізоморфними. Наприклад, коли один граф отримується з іншого підрозділенням ребра.
15. Представляючий граф називається триангуляцією відповідного одновимірного поліедру.
16. Кожному графу G {\displaystyle G} відповідає тіло графа, тобто фігура, яка отримується із скінченного числа відрізків ототожненням декількох кінців у відповідності із графом G {\displaystyle G} . Одновимірні поліедри є бієктивними з фігурами, які є топологічно еквівалентними тілу деякого графа. Наприклад, фігури | G 1 | {\displaystyle |G_{1}|} та | G 2 | {\displaystyle |G_{2}|} є топологічно еквівалентними лише у випадку, якщо графи G 1 {\displaystyle G_{1}} та G 2 {\displaystyle G_{2}} є гомеоморфними.
Граф складається з класу стрілок (орієнтованих ребер), класу об'єктів (вершин) та двох відображень
Початок: { стрілки } → → --> { об'єкти } {\displaystyle {\text{Початок:}}\{{\text{стрілки}}\}\rightarrow \{{\text{об'єкти}}\}}
Кінець : { стрілки } → → --> { об'єкти } {\displaystyle {\text{Кінець}}:\{{\text{стрілки}}\}\rightarrow \{{\text{об'єкти}}\}}
Вираз f : A ⊢ ⊢ --> B {\displaystyle f:A\vdash B} означає, що f {\displaystyle f} є стрілкою із початком A {\displaystyle A} й кінцем B ; {\displaystyle B;} таке відношення A ⊢ ⊢ --> B {\displaystyle A\vdash B} можна назвати типом f {\displaystyle f} .
Замість того, щоб писати
початок ( f ) = A , кінець ( f ) = B {\displaystyle {\text{початок}}(f)=A,\,\,{\text{кінець}}(f)=B}
пишуть f : A → → --> B , {\displaystyle f:A\rightarrow B,} або f : A ⊢ ⊢ --> B . {\displaystyle f:A\vdash B.}
Дедуктивна система є графом, який може мати наступні операції на стрілках: для кожного об'єкта A {\displaystyle A} існує стрілка тотожності (ідемпотентна):
I d A : A ⊢ ⊢ --> A {\displaystyle \mathrm {Id} _{A}:A\vdash A}
та бінарна часткова операція на стрілках (композиція), яка, застосована до стрілок f : A ⊢ ⊢ --> B {\displaystyle f:A\vdash B} та g : B ⊢ ⊢ --> C , {\displaystyle g:B\vdash C,} породжує стрілку g f : A ⊢ ⊢ --> C . {\displaystyle gf:A\vdash C.} Спеціальні стрілки відповідають аксіоматичним секвенціям й n {\displaystyle n} -арним операціям на стрілках із n ≥ ≥ --> 1 , {\displaystyle n\geq 1,} які відповідають правилам виводу. Композиція представляє собою одиничну форму правила перетину
f : A ⊢ ⊢ --> B g : B ⊢ ⊢ --> C g f : A ⊢ ⊢ --> C . {\displaystyle {\frac {f:A\vdash B\quad g:B\vdash C}{gf:A\vdash C}}.}
Відношення слідування є узагальненням відношення передпорядку на сукупності і об'єкти (або на дві сукупності об'єктів, коли відношення слідування множинно по обом сторонам, як у випадку генценівських систем класичної логіки). Відношення передпорядку є спеціальним видом дедуктивної системи, оли за кожною парою об'єктів ( A , B ) {\displaystyle (A,B)} є принамні одна стрілка із початком A {\displaystyle A} й кінцем B . {\displaystyle B.} Передвпорядковані графи виконують еквівалентність, яка має місце для кожної дедуктивної системи:
∀ ∀ --> A ∀ ∀ --> B ( ∃ ∃ --> f ( f : A ⊢ ⊢ --> B ) ⇔ ⇔ --> ∀ ∀ --> C ( ∃ ∃ --> g ( g : B ⊢ ⊢ --> C ) ⇒ ⇒ --> ∃ ∃ --> h ( h : A ⊢ ⊢ --> C ) ) ) . {\displaystyle \forall A\forall B(\exists f(f:A\vdash B)\Leftrightarrow \forall C(\exists g(g:B\vdash C)\Rightarrow \exists h(h:A\vdash C))).}
Зправа наліво це дає
∀ ∀ --> A ∃ ∃ --> f ( f : A ⊢ ⊢ --> A ) , {\displaystyle \forall A\exists f(f:A\vdash A),}
а зліва направо дає транзитивність:
∀ ∀ --> A ∀ ∀ --> B ∀ ∀ --> C ∀ ∀ --> f ∀ ∀ --> g ( ∃ ∃ --> h ( ( f : A ⊢ ⊢ --> B ) & & --> g : B ⊢ ⊢ --> C ) ⇒ ⇒ --> h : A ⊢ ⊢ --> C ) . {\displaystyle \forall A\forall B\forall C\forall f\forall g(\exists h((f:A\vdash B)\And g:B\vdash C)\Rightarrow h:A\vdash C).} Звідси по рефлексивності й транзитивності отримується стрілка тотожності й композиція стрілок.
Дедуктивна категорія є дедуктивною системою, у якій наступні рівняння між доказами мають місце:
f I d A = f , {\displaystyle f\,\mathrm {Id} _{A}=f,}
I d B f = f , {\displaystyle \mathrm {Id} _{B}\,f=f,}
( h g ) f = h ( g f ) {\displaystyle (hg)f=h(gf)}
для усіх f : A ⊢ ⊢ --> B , g : B ⊢ ⊢ --> C , h : C ⊢ ⊢ --> D . {\displaystyle f:A\vdash B,\quad g:B\vdash C,\quad h:C\vdash D.}
Перше рівняння стверджує, що композиції, тобто перетини, з одиничними стрілками є усувними, у той час як друге говорить про те, що композиції можуть змінюватися місцями одна з одною. У вільній дедуктивній категорії, яка породжена довільним графом без стрілок, композиція усувна: у цій категорії є лише стрілки тотожності. Існування таких вільних дедуктивних категорій гарантується екваціональною формою категорних аксіом. З більш абстрактної точки зору можна розглядати категорію просто як декотру структуру, коли вона представляє собою сукупність двох різновидів сутностей: об'єктів (а не формул) й стрілок або морфізмів (а не виведень з формул). Самі об'єкти також можуть мати структуру, а морфізми представляють собою відображення, які зберігають цю структуру. Найпопулярніший приклад — категорія S e t {\displaystyle \mathrm {Set} } , об'єктами якої є довільні множини, а морфізми є довільними відображеннями. Зв'язок між множинами та дедуктивними категоріями описується наступним чином: вільна абстрактна категорія, породжена довільним графом без стрілок (так звана дискретна категорія або дискрет), може розглядатися як категорне поняття множини. У подібній категорії є лише стрілки тотожності[2].
Сагайдак Q {\displaystyle Q} — це орієнтований граф ( I , E , t , h ) {\displaystyle (I,E,t,h)} , де I , E {\displaystyle I,E} — скінченновимірні множини ( E {\displaystyle E} — множина ребер графа I {\displaystyle I} — множина його вершин), t , h {\displaystyle t,h} — відображення t : E → → --> I {\displaystyle t:E\rightarrow I} та h : E → → --> I . {\displaystyle h:E\rightarrow I.} Значення t ( a ) {\displaystyle t(a)} й h ( a ) {\displaystyle h(a)} на ребрі a ∈ ∈ --> E {\displaystyle a\in E} — початок та кінець ребра a {\displaystyle a} відповідно. Можна також записати t ( a ) = i , h ( a ) = j , {\displaystyle t(a)=i,\,\,h(a)=j,} тоді a : i → → --> j {\displaystyle a:i\rightarrow j} або i → → --> a j , {\displaystyle i{\overset {a}{\rightarrow }}j,} тобто якщо a ∈ ∈ --> E {\displaystyle a\in E} — ребро з вершини i ∈ ∈ --> I {\displaystyle i\in I} у вершину j ∈ ∈ --> I . {\displaystyle j\in I.} Часто пишуть просто Q = ( I , E ) , {\displaystyle Q=(I,E),} вважаючи, що задані декотрі позначені відображення для початку та кінця кожного ребра. Можна замість a ∈ ∈ --> E {\displaystyle a\in E} записати a ∈ ∈ --> Q . {\displaystyle a\in Q.}
Розгляньмо поле комплексних чисел C . {\displaystyle \mathbb {C} .} Тоді C I {\displaystyle \mathbb {C} I} є комутативною простою алгеброю із одиницею:
1 = ∑ ∑ --> i ∈ ∈ --> I 1 i . {\displaystyle 1=\sum _{i\in I}1_{i}.}
Будь-який C I {\displaystyle \mathbb {C} I} -модуль V {\displaystyle V} розкладається у пряму суму V = ⨁ ⨁ --> i ∈ ∈ --> I V i , {\displaystyle V=\bigoplus _{i\in I}V_{i},} де V i = 1 j V . {\displaystyle V_{i}=1_{j}V.} На векторах v = ( v i ) i ∈ ∈ --> I ∈ ∈ --> V , v i ∈ ∈ --> V i , {\displaystyle v=(v_{i})_{i\in I}\in V,\,\,v_{i}\in V_{i},} алгебра C I {\displaystyle \mathbb {C} I} діє як 1 j v = ( δ δ --> i j v i ) i ∈ ∈ --> I , {\displaystyle 1_{j}v=(\delta _{ij}v_{i})_{i\in I},} та навпаки, набір векторних просторів ( V i ) i ∈ ∈ --> I {\displaystyle (V_{i})_{i\in I}} задає представлення алгебри C I {\displaystyle \mathbb {C} I} на просторі V = ⨁ ⨁ --> i ∈ ∈ --> I V i {\displaystyle V=\bigoplus _{i\in I}V_{i}} із цією дією. Зокрема, представлення сагайдака Q = ( I , E ) {\displaystyle Q=(I,E)} дає представлення C I . {\displaystyle \mathbb {C} I.}
Якщо V {\displaystyle V} є скінченновимірним, то усі V i {\displaystyle V_{i}} скінченновимірні. У цьому випадку вектор α α --> = ( α α --> ) i ∈ ∈ --> I ∈ ∈ --> Z ≥ ≥ --> 0 I {\displaystyle \alpha =(\alpha _{})_{i\in I}\in \mathbb {Z} _{\geq 0}^{I}} із компонентами α α --> i = d i m C V i {\displaystyle \alpha _{i}=\mathrm {dim} _{\mathbb {C} }V_{i}} називається розмірністю C I {\displaystyle \mathbb {C} I} -модуля. Множина усіх представлень на C I {\displaystyle \mathbb {C} I} модулі V = ⨁ ⨁ --> i ∈ ∈ --> I V i , {\displaystyle V=\bigoplus _{i\in I}V_{i},} де V i = C α α --> i , {\displaystyle V_{i}=\mathbb {C} ^{\alpha i},} узгоджених із структурою C I {\displaystyle \mathbb {C} I} -модуля, позначається R e p ( Q , α α --> ) . {\displaystyle \mathrm {Rep} (Q,\alpha ).} Щоб задати таке представлення, потрібно узяти довільний набір лінійних операторів з C α α --> i {\displaystyle \mathbb {C} ^{\alpha _{i}}} у C α α --> j {\displaystyle \mathbb {C} ^{\alpha _{j}}} для кожного ребра a : i → → --> j , {\displaystyle a:i\rightarrow j,} таким чином, отримується R e p ( Q , α α --> ) = ∏ ∏ --> a : i → → --> j H o m ( C α α --> i , C α α --> j ) {\displaystyle \mathrm {Rep} (Q,\alpha )=\prod _{a:i\rightarrow j}\mathrm {Hom} (\mathbb {C} ^{\alpha _{i}},\mathbb {C} ^{\alpha _{j}})} (добуток по усім a ∈ ∈ --> Q {\displaystyle a\in Q} ), де H o m ( C α α --> i , C α α --> j ) {\displaystyle \mathrm {Hom} (\mathbb {C} ^{\alpha _{i}},\mathbb {C} ^{\alpha _{j}})} — простір лінійних операторів з C α α --> i {\displaystyle \mathbb {C} ^{\alpha _{i}}} у C α α --> j {\displaystyle \mathbb {C} ^{\alpha _{j}}} (комплексних матриць α α --> i × × --> α α --> j {\displaystyle \alpha _{i}\times \alpha _{j}} ).
Нехай C E {\displaystyle \mathbb {C} E} — скінченновимірний векторний простір, вільно породжений множиною E , {\displaystyle E,} C E = ⨁ ⨁ --> a ∈ ∈ --> Q C a . {\displaystyle \mathbb {C} E=\bigoplus _{a\in Q}\mathbb {C} a.} На ньому існує натуральна структура C I {\displaystyle \mathbb {C} I} -бімодуля
1 k ⋅ ⋅ --> a = δ δ --> j k a , a ⋅ ⋅ --> 1 k = δ δ --> i k a ∀ ∀ --> a : i → → --> j . {\displaystyle 1_{k}\cdot a=\delta _{jk}a,\quad \quad a\cdot 1_{k}=\delta _{ik}a\quad \quad \forall a:i\rightarrow j.}
Алгебра шляхів сагайдака Q ( I , E ) {\displaystyle Q(I,E)} визначається як C Q = T C I C E , {\displaystyle \mathbb {C} Q=T_{\mathbb {C} I}\mathbb {C} E,} де T A M {\displaystyle T_{A}M} є тензорною алгеброю бімодуля M {\displaystyle M} над алгеброю A , {\displaystyle A,}
C Q = ⨁ ⨁ --> l = 0 ∞ ∞ --> ( C Q ) l , ( C Q ) 0 = C I , ( C Q ) 1 = C E , ( C Q ) 2 = C E ⊗ ⊗ --> C I C E , ( C Q ) 3 = C E ⊗ ⊗ --> C I C E ⊗ ⊗ --> C I C E , . . . {\displaystyle \mathbb {C} Q=\bigoplus _{l=0}^{\infty }(\mathbb {C} Q)_{l},\quad \quad (\mathbb {C} Q)_{0}=\mathbb {C} I,\quad \quad (\mathbb {C} Q)_{1}=\mathbb {C} E,\quad \quad (\mathbb {C} Q)_{2}=\mathbb {C} E\otimes _{\mathbb {C} I}\mathbb {C} E,\quad \quad (\mathbb {C} Q)_{3}=\mathbb {C} E\otimes _{\mathbb {C} I}\mathbb {C} E\otimes _{\mathbb {C} I}\mathbb {C} E,...}
Лінійний простір ( C Q ) l , l ≥ ≥ --> 0 , {\displaystyle (\mathbb {C} Q)_{l},\,\,l\geq 0,} вільно породжений елементами виду a l , ⋅ ⋅ --> ⋅ ⋅ --> ⋅ ⋅ --> a 2 a 2 1 i 0 , {\displaystyle a_{l},\cdot \cdot \cdot a_{2}a_{2}1_{i_{0}},} де a k : i k − − --> 1 → → --> i k {\displaystyle a_{k}:i_{k-1}\rightarrow i_{k}} є ребрами, які послідово йдуть між вершинами i 0 , i 1 , . . . , i l ∈ ∈ --> I . {\displaystyle i_{0},i_{1},...,i_{l}\in I.} [3] Алгебра шляхів сагайдака є алгеброю із одиницею
1 = ∑ ∑ --> i ∈ ∈ --> I e i , {\displaystyle 1=\sum _{i\in I}e_{i},}
де e i {\displaystyle e_{i}} — шлях довжини нуль із початком та кінцем у вершині i . {\displaystyle i.}
Нехай k {\displaystyle k} — довільне алгебрично замкнене поле, тоді k Q {\displaystyle kQ} — алгебра шляхів сагайдака, яка може бути розглянута як градуйована алгебра, l {\displaystyle l} -та компонента якої породжується шляхами довжини l . {\displaystyle l.} Якщо I {\displaystyle {\mathfrak {I}}} — однорідний ідеал алгебри k Q {\displaystyle kQ} , то на алгебрі A = k Q / I {\displaystyle A=kQ/{\mathfrak {I}}} успадковується структура градуйованої алгебри A = ⨁ ⨁ --> l ≥ ≥ --> 0 A l . {\displaystyle A=\bigoplus _{l\geq 0}A_{l}.} [4]
Нехай A = k Q / I {\displaystyle A=kQ/{\mathfrak {I}}} — алгебра шляхів сагайдака та фроберіусовою формою ε ε --> : A → → --> k {\displaystyle \varepsilon :A\rightarrow k} , Фробеніусова форма ε ε --> {\displaystyle \varepsilon } називається Q 0 {\displaystyle Q_{0}} -формою, якщо існує k Q 0 {\displaystyle kQ_{0}} -бімодуль T ≤ ≤ --> K e r ( ε ε --> ) {\displaystyle T\leq \mathrm {Ker} (\varepsilon )} такий, що A = s o c ( A ) ⊕ ⊕ --> T . {\displaystyle A=\mathrm {soc} (A)\oplus T.} Якщо A = k Q / I {\displaystyle A=kQ/I} — самоін'єктивна алгебра шляхів сагайдака, ε ε --> : A → → --> k {\displaystyle \varepsilon :A\rightarrow k} — Q 0 {\displaystyle Q_{0}} -форма на A , {\displaystyle A,} v ~ ~ --> = A → → --> A {\displaystyle {\tilde {v}}=A\rightarrow A} — відповідний автоморфізм Накаями[5], ϱ ϱ --> : A → → --> A ⊗ ⊗ --> A {\displaystyle \varrho :A\rightarrow A\otimes A} — фробеніусовий кодобуток, тоді ν ν --> ~ ~ --> ( e i ) = e ν ν --> 0 ( i ) ∀ ∀ --> i ∈ ∈ --> Q 0 , I m ( ϱ ϱ --> ) ≤ ≤ --> ⨁ ⨁ --> i ∈ ∈ --> Q 0 P ν ν --> 0 ( i ) , i , {\displaystyle {\tilde {\nu }}(e_{i})=e_{\nu _{0}(i)}\,\,\,\forall i\in Q_{0},\,\,\mathrm {Im} (\varrho )\leq \bigoplus _{i\in Q_{0}}P_{\nu _{0}(i),i},} причому
ϱ ϱ --> ′ : A → → --> ⨁ ⨁ --> i ∈ ∈ --> Q 0 P ν ν --> 0 ( i ) , i , {\displaystyle \varrho ':A\rightarrow \bigoplus _{i\in Q_{0}}P_{\nu _{0}(i),i},}
де ϱ ϱ --> ′ ( a ) = ϱ ϱ --> ( a ) {\displaystyle \varrho '(a)=\varrho (a)} — ін'єктивна оболонка бімодулю A . {\displaystyle A.}
Якщо M {\displaystyle M} — A {\displaystyle A} -модуль, то через r a d k ( M ) {\displaystyle \mathrm {rad} ^{k}(M)} позначається k {\displaystyle k} -тий член радіального ряду M = r a d 0 ( M ) ⊇ ⊇ --> r a d 1 ( M ) ⊇ ⊇ --> . . . {\displaystyle M=\mathrm {rad} ^{0}(M)\supseteq \mathrm {rad} ^{1}(M)\supseteq ...} та через s o c k ( M ) k {\displaystyle \mathrm {soc} ^{k}(M)\,\,\,k} -тий член цокольного ряду 0 = s o c 0 ( M ) ⊆ ⊆ --> s o c 1 ( M ) ⊆ ⊆ --> . . . {\displaystyle 0=\mathrm {soc} ^{0}(M)\subseteq \mathrm {soc} ^{1}(M)\subseteq ...} Для k < 0 {\displaystyle k<0} будемо вважати, що s o c k ( M ) = 0 {\displaystyle \mathrm {soc} ^{k}(M)=0} та r a d k ( M ) = M . {\displaystyle \mathrm {rad} ^{k}(M)=M.} Нехай I {\displaystyle {\mathfrak {I}}} — однорідний припустимий ідеал алгебри шляхів k Q , A = k Q / I {\displaystyle kQ,\,\,A=kQ/{\mathfrak {I}}} та P i = e i A . {\displaystyle P_{i}=e_{i}A.} Тоді
r a d k ( P i ) = ⨁ ⨁ --> l ≥ ≥ --> k e i A l . {\displaystyle \mathrm {rad} ^{k}(P_{i})=\bigoplus _{l\geq k}e_{i}A_{l}.}
Якщо алгебра A {\displaystyle A} є самоін'єктивною і довжина Леві модулю P i {\displaystyle P_{i}} дорівнює m , {\displaystyle m,} то[4]
s o c k ( P i ) = r a d m − − --> k ( P i ) . {\displaystyle \mathrm {soc} ^{k}(P_{i})=\mathrm {rad} ^{m-k}(P_{i}).}
Родоначальником теорії графів вважається Леонард Ейлер. У 1736 році в одному зі своїх листів він формулює і пропонує розв'язок задачі про сім Кенігсберзьких мостів, що стала згодом однією з класичних задач теорії графів.
Поштовх до розвитку теорія графів отримала на рубежі XIX і ХХ століть, коли різко зросла кількість робіт в сфері топології та комбінаторики, з якими її пов'язують тісні узи спорідненості. Графи стали використовуватися при побудові схем електричних кіл і молекулярних схем. Як окрема математична дисципліна теорія графів була вперше представлена в роботі угорського математика Кеніга в 30-ті роки XX століття.
Останнім часом графи і пов'язані з ними методи досліджень органічно пронизують на різних рівнях чи не всю сучасну математику. Теорія графів розглядається як одна з гілок топології; безпосереднє відношення вона має також до алгебри і до теорії чисел. Графи ефективно використовуються в теорії планування та управління, теорії розкладів, соціології, математичній лінгвістиці, економіці, біології, медицині, географії. Широке застосування знаходять графи в таких областях, як програмування, теорія кінцевих автоматів, електроніка, в рішенні імовірнісних і комбінаторних задач, знаходженні максимального потоку в мережі, найкоротшої відстані, максимального паросполучення, перевірки планарності графа та ін. Як особливий клас можна виділити задачі оптимізації на графах. Математичні розваги і головоломки теж є частиною теорії графів, наприклад, знаменита проблема чотирьох фарб, інтригуюча математиків і по сей день. Теорія графів швидко розвивається, знаходить все нові додатки і чекає молодих дослідників.
Термінологія теорії графів не визначена суворо. Зокрема в монографії Гудман, Хідетніемі, 1981 сказано: "У програмістському світі немає єдиної думки про вибір з двох термінів «граф» або «мережа».
Зв'язний граф називається ейлеровим графом, якщо існує замкнений ланцюг, який проходить через кожне ребро. Такий ланцюг називатимемо ейлеровим ланцюгом, або ейлеровим циклом.
Граф називається напівейлеровим, якщо існує ланцюг, який проходить через кожне його ребро рівно один раз.
Лісом називається граф, який не містить циклів. Зв'язний ліс називається деревом.
Плоским графом називається граф, у діаграмі якого лінії, що відповідають ребрам, перетинаються лише в точках, які відповідають вершинам графа.
Планарним графом називається граф G, ізоморфний деякому плоскому графу. Останній називається плоскою картою графа G.
Внутрішньою гранню плоского зв'язного графа називається скінченна область площини, що обмежена замкненим маршрутом графа і не містить усередині ні вершин, ні ребер графа. Частина площини, яка складається з точок, що не належать жодній внутрішній грані, називається зовнішньою гранню.
Множина всіх граней плоского зв'язного графа позначається P. Замкнений маршрут, що обмежує грань, називається межею грані, а довжина цього маршруту — степенем грані. Степінь грані позначається Pr.
Максимальним планарним графом називається планарний граф, який при додаванні до нього будь-якого ребра перестає бути планарним.
Плоский зв'язний граф, кожна грань якого (включаючи й зовнішню) обмежена трикутником, називається триангуляцією.
При зображенні графів найчастіше використовується така система позначень: кожна вершина зображується у вигляді точки на площині, і якщо між вершинами існує ребро, то відповідні точки з'єднуються відрізком. У разі орієнтованого графа відрізки замінюють стрілками або явно показують напрямок ребра. Розрізняють планарні і непланарні графи. Планарний граф — це граф, який можна зобразити на малюнку без пересікання ребер (найпростіші — трикутник або пара пов'язаних вершин), інакше — непланарний. У випадку коли граф не містить циклів (шляхів однократного обходу ребер і вершин з поверненням у вихідну точку), його прийнято називати «деревом». Важливі види дерев в теорії графів — бінарні дерева, де кожна вершина має одне вхідне ребро і рівно два вихідних, або є кінцевою — не має вихідних ребер.
Не слід плутати зображення графа із власне графом (абстрактною структурою), оскільки одному графу можна зіставити не одне графічне представлення. Зображення покликане лише показати, які пари вершин з'єднані ребрами, а які — ні. Часто на практиці буває важко відповісти на питання, чи є два зображення моделями одного і того ж графа, чи ні. Залежно від завдання, одні зображення можуть давати більш наочну картину, ніж другі.
До теорії графів також відноситься цілий ряд математичних проблем, не вирішених на сьогоднішній день.
بن اسلق الصغرى تقسيم إداري البلد المغرب الجهة فاس مكناس الإقليم مولاي يعقوب الدائرة أولاد جمعة لمطة الجماعة القروية عين بوعلي المشيخة كبكب السكان التعداد السكاني 116 نسمة (إحصاء 2004) • عدد الأسر 15 معلومات أخرى التوقيت ت ع م±00:00 (توقيت قياسي)[1]، وت ع م+01:00 (توقيت صيف…
село Ставки Країна Україна Область Одеська область Район Одеський район Громада Доброславська селищна громада Код КАТОТТГ UA51100170100064509 Основні дані Засноване 1940 Населення 175 Площа 0,27 км² Густота населення 648,15 осіб/км² Поштовий індекс 67520 Телефонний код +380 4855 Ге
1978 live album by Clifford Jordan & The Magic TriangleOn Stage Vol. 2Live album by Clifford Jordan & The Magic TriangleReleased1978RecordedMarch 29, 1975The Bimhaus, Amsterdam, HollandGenreJazzLength42:20LabelSteepleChaseSCS-1092 ProducerNils WintherClifford Jordan chronology On Stage Vol. 1(1975) On Stage Vol. 2(1978) On Stage Vol. 3(1975) On Stage Vol. 2 is a live album by saxophonist Clifford Jordan which was recorded in Holland in 1975 and first released on the SteepleChase …
New Zealand regional rugby union governing body Tasman Rugby UnionSportRugby unionAbbreviationTRUFounded2006; 17 years ago (2006)AffiliationNew Zealand RugbyRegional affiliationTasman Bay / Te Tai-o-AorereHeadquartersNelsonOfficial websitewww.tasmanrugby.co.nz The Tasman Rugby Union is the governing body for rugby union in Tasman Bay / Te Tai-o-Aorere, a bay at the north end of the South Island in New Zealand. Headquartered in Nelson, TRU is New Zealand's newest provincial unio…
ФіліппНародився 4 століття до н. е.Помер 318 до н. е.Діяльність губернаторПосада сатрап Філіпп (дав.-гр. Φιλιππoς ; страчений в 318 до н. е.) — македонський воєначальник, сатрап Согдіани, а потім Парфії Карта поділу імперії Ахеменідів на сатрапії Біографія Очевидно,
W.27 and W.32 Hansa-Brandenburg W.27 Role Fighter floatplaneType of aircraft National origin Germany Manufacturer Hansa-Brandenburg Number built 2 The Hansa Brandenburg W.27 and W.32 were prototype fighter floatplanes developed in parallel in Germany during World War I. They were developments of and intended replacements for the W.12 then in service and differed from each other principally in the choice of powerplant, the W.27 with a Benz Bz.IIIb and the W.32 with the same Mercedes D.III that th…
State of Nigeria State in NigeriaTaraba TarabaStateMambilla Plateau of Taraba State SealNicknames: Nature's Gift to the Nation (French: Le cadeau de la nature à la nation)Location of Taraba State in NigeriaCoordinates: 8°00′N 10°30′E / 8.000°N 10.500°E / 8.000; 10.500Country NigeriaDate created27 August 1991CapitalJalingoGovernment • BodyGovernment of Taraba State • Governor (List)Agbu Kefas (PDP) • Deputy GovernorAmi…
ساميان - قرية - تقسيم إداري البلد إيران المحافظة أردبيل المقاطعة مقاطعة أردبيل الناحية الناحية المركزية القسم الريفي قسم کلخوران الريفي إحداثيات 38°22′19″N 48°14′37″E / 38.37194°N 48.24361°E / 38.37194; 48.24361 السكان التعداد السكاني 891 نسمة (إحصاء 2016) معلومات أخرى ال
Mitsubishi Electric Halle Mitsubishi Electric Halle Nomes Nome Mitsubishi Electric Halle Antigos nomes Philips Halle (1971-2011) Características Local Düsseldorf, Alemanha Capacidade 7,500 Inauguração Data 1971 (52 anos) Proprietário Cidade de Düsseldorf Administrador Düsseldorf Congress Sport & Event Vista externa da então Philipshalle Mitsubishi Electric Halle é uma arena multi-uso localizada em Düsseldorf, Alemanha.[1] Foi inaugurada em 1971 com o nome Philips Hal…
توماس ماك آرثر أندرسون معلومات شخصية الميلاد 21 يناير 1836(1836-01-21)تشيليكوث، أوهايو الوفاة 8 مايو 1917 (81 سنة)بورتلاند، أوريغون مكان الدفن مقبرة أرلينغتون الوطنية مواطنة الولايات المتحدة أقرباء روبرت أندرسون (عم)[1] الحياة العملية المدرسة الأم جامعة جبل القديسة مريم…
Resident Evil 6 Información generalDesarrollador CapcomDistribuidor CapcomDiseñador Jiro TaokaDirector Eiichiro SasakiProductor Yoshiaki HirabayashiProgramador Soji SetaArtista Tomoroni TakanoEscritor Shotaro SugaCompositor Akihiko NaritaAkiyuki MorimotoAzusa KatoKota SuzukiThomas ParischLaurent ZilianiDaniel LindholmSebastian SchwartzDatos del juegoGénero TerrorDisparos en tercera personaAcción-AventuraIdiomas inglés, francés, alemán, italiano, polaco, portugués brasileño, español y r…
Нові Білокоровичі Коростенська дирекція Південно-Західна залізниця зупинний пунктРозташуванняРозташування с. БілокоровичіКоординати 51°07′21″ пн. ш. 28°01′17″ сх. д. / 51.12250° пн. ш. 28.02139° сх. д. / 51.12250; 28.02139СтруктураЛінія(ї) Коростень — Ол…
Refugio de vida silvestre Bosques Nublados de Udima Bosques nublados de Udima, Santa Cruz.SituaciónPaís Perú PerúDivisión CajamarcaSubdivisión Provincia de Santa CruzCoordenadas 6°49′34″S 79°02′24″O / -6.826144, -79.039883Datos generalesFecha de creación 1 de febrero de 2010Legislación (D.S. N.º 020-2011-MINAM)Superficie 12 183.20 ha Refugio de vida silvestre Bosques Nublados de Udima Ubicación en Perú.Sitio web oficial[editar datos en Wikidata…
Другуска 54°00′59″ пн. ш. 35°26′43″ сх. д. / 54.01666500002777838° пн. ш. 35.44530600002777732° сх. д. / 54.01666500002777838; 35.44530600002777732Витік у селі Ушаково• координати 54°00′15″ пн. ш. 35°27′38″ сх. д. / 54.00417° пн. ш. 35.46056° сх. д. / 54.00417; 35.46056Гирло Жиз…
Paus Benediktus XVI, Januari 2006 Kotbah Regensburg atau pernyataan Regensburg disampaikan pada 12 September 2006 oleh Paus Benediktus XVI di Universitas Regensburg, Jerman, dimana ia sempat menjabat sebagai profesor teologi. Kotbah tersebut diberi judul Iman, Nalar dan Universitas — Kenangan dan Renungan (Jerman: Glaube, Vernunft und Universität — Erinnerungen und Reflexionen). Kotbah tersebut dianggap sebagai salah satu pernyataan kepausan paling berpengaruh di dunia sejak pernyataan …
Untuk kegunaan lain, lihat Hardtop (disambiguasi). Artikel atau beberapa bagian di dalam artikel ini membingungkan atau bergaya propaganda dan/atau indoktrinasi kepada pembaca. Tolong bantu memperbaiki artikel ini, dengan memberikan sumber referensi yang tepercaya. 1982 Daihatsu Taft (F50JV) hardtop Hardtop adalah bentuk atap mobil yang kaku, yang untuk mobil modern biasanya terbuat dari logam. Atap hardtop dapat diperbaiki (yaitu tidak dapat dilepas), dapat dilepas untuk penyimpanan terpisah at…
Kolkata Municipal Corporation in West Bengal, IndiaWard No. 90Kolkata Municipal CorporationInteractive Map Outlining Ward No. 90Ward No. 90Location in KolkataCoordinates (dms): 22°30′51″N 88°22′00″E / 22.514222°N 88.366694°E / 22.514222; 88.366694Country IndiaStateWest BengalCityKolkataNeighbourhoodsBallygunge (Lake Terrace), Rabindra Sarobar, Dhakuria (South End Park-Kankulia)ReservationWomen(Open)Parliamentary constituencyKolkata DakshinAssembly con…
لمعانٍ أخرى، طالع الواسطة (توضيح). قرية الواسطة - قرية - تقسيم إداري البلد اليمن المحافظة محافظة المحويت المديرية مديرية ملحان العزلة عزلة العسوس السكان التعداد السكاني 2004 السكان 486 • الذكور 227 • الإناث 259 • عدد الأسر 59 • عدد المساكن 58 معل
Willi Wülbeck campeão mundial Atletismo Nome completo Wilhelm Wülbeck Modalidade 800 metros Nascimento 18 de dezembro de 1954 (68 anos)Oberhausen, Alemanha(ex-Alemanha Ocidental) Nacionalidade alemão Medalhas Competidor da Alemanha Ocidental Campeonatos Mundiais Ouro Helsínquia 1983 800 metros Taça do Mundo Bronze Düsseldorf 1977 800 metros Bronze Montreal 1979 800 metros Taça da Europa - Final A Ouro Helsínquia 1977 800 metros Ouro Londres 1983 800 metros Prata Zagreb 1981 80…
小野塚 喜平次 人物情報生誕 (1871-02-10) 1871年2月10日 日本 柏崎県古志郡長岡城下上田町(現:新潟県長岡市上田町)死没 (1944-11-27) 1944年11月27日(73歳没)出身校 東京帝国大学学問研究分野 政治学研究機関 東京帝国大学テンプレートを表示 小野塚喜平次 小野塚 喜平次(おのづか きへいじ、1871年2月10日〈明治3年12月21日[1]〉 - 1944年〈昭和19年〉11月27日[1][2]…
Lokasi Pengunjung: 3.128.200.132