Кіріспе
Граф теориясының негізгі ұғымы
Математика мен компьютерлік ғылымда байланыстылық – граф теориясының негізгі ұғымдарының бірі болып табылады: ол қалған түйіндерді екі немесе одан көп оқшауланған кішкентай графтарға бөлу үшін қанша элементті (түйіндерді немесе қабырғаларды) жою қажет екенін анықтайды. Егер кез келген u және v төбелері үшін u-ден v-ге және v-ден u-ге бағытталған жол болса, онда граф күшті байланысты деп немесе жай ғана күшті деп аталады.
Құрамында бөліктер мен бөлшектер
Байланысты компонент – бағытталмаған графтың ең үлкен байланысқан субграфы. Әрбір төбе дәл бір байланысқан компонентке тиесілі, әр қабырға сияқты. Граф байланысқан болса, және тек қана оның дәл бір байланысқан компоненті болса. Күшті компоненттер – бағытталған графтың ең үлкен, күшті байланысқан субграфтары. Бір-бірімен байланысқан G графының кесілген немесе бөлінетін төбелер жиыны – бұл G-ді ажыратып тастайтын төбелер жиыны. Төбелік байланыс κ(G) (G толық граф емес болса) – ең кішкентай кесілгеннің мөлшері. Графтың төбелік байланысы k немесе одан үлкен болса, онда ол k-төбелік байланысқан граф деп аталады. Нақтырақ айтқанда, кез келген G графы (толық немесе емес) k-төбелік байланысқан деп аталады, егер онда кем дегенде k + 1 төбе болса, бірақ k - 1 төбелер жиыны болмаса, оларды алып тастау графы ажыратып тастайды; және κ(G) – G k-төбелік байланысқан болатын ең үлкен k ретінде анықталады. Атап айтқанда, Kn деп белгіленетін n төбесі бар толық графтың төбелік кесілуі жоқ, бірақ u және v екі төбесі үшін төбелік кесілу – бұл төбелер жиыны, оларды графтан алып тастау u және v-ді ажыратады. Жергілікті төбелік байланыс κ(u, v) – u және v-ді ажырататын ең кішкентай төбелік кесілудің мөлшері. Жергілікті төбелік байланыс бағытталмаған графтар үшін симметриялық; яғни, толық графтарды қоспағанда, κ(G) – u, v төбелерінің барлық жанындас емес жұптары бойынша κ(u, v)-ның ең кішісіне тең. 2-байланыс – екі байланыстылық, ал 3-байланыс – үш байланыстылық деп аталады. 2-байланысқан, бірақ байланыспаған G графы кейде бөлінетін деп аталады. Шеттерге қатысты ұқсас ұғымдарды анықтауға болады. Бір ғана, белгілі бір қабырғаны кесу графы ажыратып тастайтын қарапайым жағдайда, бұл қабырға көпір деп аталады. Жалпы алғанда, G-нің қабырға кесілуі – қабырғалар жиыны, оларды алып тастау графы ажыратып жібереді. Қабырғалық байланыс λ(G) – ең кішкентай қабырға кесілуінің мөлшері, ал екі төбе u, v-нің жергілікті қабырғалық байланысы λ(u, v) – u-ді v-ден ажырататын ең кішкентай қабырға кесілуінің мөлшері. Тағы да, жергілікті қабырғалық байланыс симметриялық. Графтың қабырғалық байланысы k немесе одан үлкен болса, онда ол k-қабырғалық байланысқан граф деп аталады. Графтың байланыстылығы оның ең төменгі дәрежесіне тең болса, онда ол максималды байланысқан граф деп аталады. Графтың қабырғалық байланыстылығы оның ең төменгі дәрежесіне тең болса, онда ол максималды қабырғалық байланысқан граф деп аталады.
A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. The local connectivity κ(u, v) is the size of a smallest vertex cut separating u and v. Local connectivity is symmetric for undirected graphs; that is, Moreover, except for complete graphs, κ(G) equals the minimum of κ(u, v) over all nonadjacent pairs of vertices u, v.
2 connectivity is also called biconnectivity and 3 connectivity is also called triconnectivity. A graph G which is connected but not 2 connected is sometimes called separable. Analogous concepts can be defined for edges. In the simple case in which cutting a single, specific edge would disconnect the graph, that edge is called a bridge. More generally, an edge cut of G is a set of edges whose removal renders the graph disconnected. The edge connectivity λ(G) is the size of a smallest edge cut, and the local edge connectivity λ(u, v) of two vertices u, v is the size of a smallest edge cut disconnecting u from v. Again, local edge connectivity is symmetric. A graph is called k edge connected if its edge connectivity is k or greater. A graph is said to be maximally connected if its connectivity equals its minimum degree. A graph is said to be maximally edge connected if its edge connectivity equals its minimum degree.
Супер және гипер байланыс
График, егер әрбір ең кіші төбелік кесігі бір төбені оқшауласа, супер байланысқан немесе супер κ деп аталады. График, егер әрбір ең кіші төбелік кесігін жою дәл екі компонентті құрса, олардың бірі оқшауланған төбе болса, гипер байланысқан немесе гипер κ деп аталады. График, егер кез келген ең кіші төбелік кесігі оны дәл екі компонентке бөлсе, жартылай гипер байланысқан немесе жартылай гипер κ деп аталады. Нақтырақ айтқанда: G байланысқан графигі, егер барлық ең кіші төбелік кесіктері бір (ең төменгі дәрежелі) төбемен іргелес төбелерден тұрса, супер байланысқан немесе супер κ деп аталады. G байланысқан графигі, егер барлық ең кіші жиектік кесіктері кейбір (ең төменгі дәрежелі) төбеге тиісті жиектерден тұрса, супер жиекті байланысқан немесе супер λ деп аталады. G графигінің кесіндісі X, егер X-те кез келген X-ке тиісті емес u төбесінің N(u) көршілігі болмаса, тривиальды емес кесінді деп аталады. Онда G графигінің супербайланыстылығы – . Тривиальды емес жиектік кесінді және жиектің супербайланыстылығы ұқсас анықталады.
A non trivial edge cut and the edge superconnectivity are defined analogously.
Менгер теоремасы
Графтардағы байланыстылық туралы ең маңызды фактілердің бірі – Менгер теоремасы, ол графтың байланыстылығы мен қабырғалық байланыстылығын төбелер арасындағы тәуелсіз жолдар саны арқылы сипаттайды. Егер u және v – G графының төбелері болса, онда u мен v арасындағы жолдар жиыны тәуелсіз деп аталады, егер олардың екеуі де бір төбемен (u және v төбелерінен басқа) ортақ болмаса. Сол сияқты, жиын қабырғалық тәуелсіз болады, егер оның екі жолы да бір қабырғамен ортақ болмаса. u және v арасындағы өзара тәуелсіз жолдар саны κ′(u, v) деп белгіленеді, ал u және v арасындағы өзара қабырғалық тәуелсіз жолдар саны λ′(u, v) деп белгіленеді. Менгер теоремасы бойынша, егер u және v – әртүрлі төбелер болса, онда λ(u, v) = λ′(u, v), ал егер u, v төбесіне іргелес болмаса, онда κ(u, v) = κ′(u, v). Бұл фактінің өзі – Max flow min cut теоремасының ерекше жағдайы.
Есептеу аспектілері
Графиктегі екі төбе байланысты ма, жоқ па, деген мәселені іздеу алгоритмі арқылы, мысалы, ендігі бірінші іздеу арқылы тиімді шешуге болады. Жалпы алғанда, графтың байланысты екенін есептеу арқылы анықтау оңай (мысалы, ажыратылған жиын дерек құрылымын пайдалану арқылы) немесе байланысқан компоненттердің санын санау мүмкін. Қарапайым алгоритмді псевдокодта былай жазуға болады:
Граф G-нің кез келген кездейсоқ төбесінен бастаңыз.
Ол төбеден тереңдікті бірінші немесе ендігі бірінші іздеуді қолданып, барлық төбелерді санап, өтіңіз. Граф толығымен қарастырылғаннан кейін, егер саналған төбелердің саны G төбелерінің санына тең болса, граф байланысқан; әйтпесе, ол ажыратылған. Менгер теоремасы бойынша, байланысқан граф G-дегі кез келген екі u және v төбесі үшін κ(u, v) және λ(u, v) сандарын максималды ағын мен минималды кесім алгоритмін қолдану арқылы тиімді анықтауға болады. G-нің байланыстылығы және қабырғалық байланыстылығы κ(u, v) және λ(u, v) ең төменгі мәндері ретінде есептеледі. Есептеу күрделілігі теориясында SL – бұл графиктегі екі төбе байланысқандығын анықтау мәселесіне логарифмдік кеңістікте келтірілетін мәселелер класы. Бұл мәселені 2004 жылы Омер Рейнгольд L класына тең деп дәлелдеді. Сондықтан, бағытталмаған графтың байланыстылығы O(log n) кеңістікте шешілуі мүмкін. Бернуллидің кездейсоқ графигінің байланысты болу ықтималдығын есептеу мәселесі желілік сенімділік деп аталады, ал екі берілген төбе байланысқандығын анықтау мәселесі ST сенімділік мәселесі деп аталады. Бұл екеуі де #P қиын.
Proceed from that node using either depth first or breadth first search, counting all nodes reached. Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of G, the graph is connected; otherwise it is disconnected. By Menger's theorem, for any two vertices u and v in a connected graph G, the numbers κ(u, v) and λ(u, v) can be determined efficiently using the max flow min cut algorithm. The connectivity and edge connectivity of G can then be computed as the minimum values of κ(u, v) and λ(u, v), respectively. In computational complexity theory, SL is the class of problems log space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004. Hence, undirected graph connectivity may be solved in O(log n) space. The problem of computing the probability that a Bernoulli random graph is connected is called network reliability and the problem of computing whether two given vertices are connected the ST reliability problem. Both of these are #P hard.
Мысалдар
Үзіліссіз графтың төбелік және жиектік байланыстылығы 0-ге тең. 1-байланыстылық, кем дегенде екі төбесі бар графтар үшін байланыстылыққа тең. N төбесі бар толық графтың жиек байланыстылығы n - 1-ге тең. N төбесі бар басқа қарапайым графтардың жиек байланыстылығы қатаң түрде кішідірек. Ағашта кез келген екі әртүрлі төбе арасындағы жергілікті жиек байланыстылығы 1-ге тең.
Қосылымның шектері
Графтың төбелік байланысы оның қабырғалық байланысынан кем немесе тең болады. Яғни, κ(G) ≤ λ(G). Кемінде 2 төбесі бар графтың қабырғалық байланысы, графтың ең төмен дәрежесіне тең немесе одан кем болады, себебі ең төмен дәрежелі төбесіне жанасқан барлық қабырғаларды жою, сол төбені графтың қалған бөлігінен бөліп тастайды. d дәрежелі төбелік транзитивті граф үшін: d ≤ 4 дәрежелі төбелік транзитивті граф үшін, немесе d дәрежелі кез келген (бағытталмаған) минималды Кейли графигі үшін, немесе d дәрежелі кез келген симметриялық граф үшін, екі түрлі байланыс та тең болады: .
Басқа қасиеттері
Байланыстылық граф гомоморфизмдері арқылы сақталады. Егер G графигі байланысқан болса, онда оның сызықтық графигі L(G) да байланысқан болады. G графигі 2 қабырғамен байланысқан, егер және тек қана егер оның бағытталған түрі күшті байланысқан болса. Балинский теоремасы бойынша, k өлшемді дөңгелек политоптың политопальды графигі (1-скелеті) k төбелі байланысқан график болып табылады. Штейнц теоремасының бұрынғы тұжырымы, кез келген 3 төбелі байланысқан жазық график политопальды график болып табылады, бұл теорема ішінара кері тұжырым береді. Г.А. Дирак теоремасына сәйкес, егер граф k ≥ 2 үшін k- байланысқан болса, онда графтың әрбір k төбелі жиыны үшін осы жиынның барлық төбелерінен өтетін цикл болады. Кері тұжырым .