Екі байланысқан график - Biconnected graph
| Тиісті тақырыптар |
| Графикалық байланыс |
|---|
Жылы графтар теориясы, а қосарланған график байланысты және «бөлінбейтін» график деген мағынаны білдіреді шың жою керек еді, график байланыста қалады. Сондықтан қосарланған графикте жоқ артикуляция шыңдары.
Болу қасиеті 2-қосылған қосылғыштығына тең, тек егер толық граф екі шыңның екеуі әдетте 2-байланыстырылған деп саналмайды.
Бұл қасиет, әсіресе, екі еселі графиканы жүргізуде пайдалы қысқарту, біреуін алып тастаған кезде ажыратудың алдын алу үшін шеті (немесе байланыс).
Пайдалану қосарланған графиктер желілік байланыста өте маңызды (қараңыз) Желілік ағын ), артықшылықтың осы қасиетіне байланысты.
Анықтама
A қосарланған бағытталмаған граф - бұл кез-келген жалғыз шыңды (және оның түскен шеттерін) өшіру арқылы ажыратылмаған бөліктерге бөлінбейтін қосылған график.
A қосарланған бағытталған граф кез-келген екі шыңға арналған v және w бастап бағытталған екі жол бар v дейін w басқаларынан басқа ортақ шыңдары жоқ v және w.
| Тік | Мүмкіндіктер саны |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
| 4 | 3 |
| 5 | 10 |
| 6 | 56 |
| 7 | 468 |
| 8 | 7123 |
| 9 | 194066 |
| 10 | 9743542 |
| 11 | 900969091 |
| 12 | 153620333545 |
| 13 | 48432939150704 |
| 14 | 28361824488394169 |
| 15 | 30995890806033380784 |
| 16 | 63501635429109597504951 |
| 17 | 244852079292073376010411280 |
| 18 | 1783160594069429925952824734641 |
| 19 | 24603887051350945867492816663958981 |
Мысалдар
Төрт шың мен төрт шеттегі қосарланған график
Екі байланыссыз граф. Х шыңын жою графикті ажыратады.
Бес шыңда және алты шетте қосарланған график
Екі байланыссыз граф. Х шыңын жою графикті ажыратады.
Сондай-ақ қараңыз
Пайдаланылған әдебиеттер
- Эрик В.Вейштейн. «Қос байланысқан график.» MathWorld - Wolfram веб-ресурсы. http://mathworld.wolfram.com/BiconnectedGraph.html
- Пол Э. Блэк, «қосарланған график», алгоритмдер және мәліметтер құрылымы сөздігінде [онлайн], Пол Э.Блэк, басылым, АҚШ ұлттық стандарттар және технологиялар институты. 17 желтоқсан 2004. (БҮГІН қол жеткізілді): https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html
Сыртқы сілтемелер
- Байланыстырылған Java компоненттерінің ағашы jBPT кітапханасында (BCTree сыныбын қараңыз).