|
bool isupper(int v1, int v2) {
return tin[v1] <= tin[v2] && tout[v1] >= tout[v2];
}
int isfather(int v1, int v2) {
if (isupper(v1, v2))
return 1;
if (isupper(v2, v1))
return -1;
return 0;
}
41..Graf komponentlari.
Graflar nazariyasida, ba'zan boshqarilmaydigan grafning tarkibiy qismi deb ataladigan tarkibiy qism - bu har qanday ikki uchi bir-biri bilan yo'llar orqali bog'langan va supergrafdagi qo'shimcha cho'qqilar bilan bog'liq bo'lmagan subgraf. Masalan, rasmda ko'rsatilgan graf uchta komponentdan iborat. Hodisa qirralari bo'lmagan vertex o'zi tarkibiy qismdir. O'ziga bog'langan graf butun grafdan tashkil topgan bitta tarkibiy qismga ega.
Ekvivalentlik munosabati
Komponentlarni aniqlashning alternativ usuli grafikning uchida aniqlangan ekvivalentlik munosabatlarining ekvivalentlik sinflarini o'z ichiga oladi. Yo'naltirilmagan grafikda v uchidan v-ga vertikal yo'nalish orqali o'tish mumkin, agar u-dan v-gacha bo'lgan yo'l bo'lsa. Ushbu ta'rifda bitta uchi uzunligi nol uzunligi deb hisoblanadi va shu vertex ichida bir necha marta bo'lishi mumkin. yo'l.
Ruxsat berish - bu ekvivalentlik munosabati, chunki: Bu refleksli: har qanday tepadan o'zgacha nol uzunlikdagi trivial yo'l mavjud.
Bu nosimmetrikdir: agar u dan v gacha bo'lgan yo'l bo'lsa, xuddi shu qirralar v dan u gacha bo'lgan yo'lni hosil qiladi.
U o'tuvchan bo'ladi: agar u dan v gacha bo'lgan yo'l va v dan wgacha bo'lgan yo'l bo'lsa, u dan vgacha bo'lgan yo'lni hosil qilish uchun ikkita yo'l bir-biriga ulanishi mumkin. Keyin tarkibiy qismlar bu munosabatlarning ekvivalentlik sinflari tomonidan yaratilgan induktsiya qilingan subgraflardir.
Komponentlar soni .
Komponentlar soni grafning muhim topologik invariantidir. Topologik graf nazariyasida bu grafikning netto Betti raqami sifatida talqin qilinishi mumkin. Algebraik graf nazariyasida u 0 ning ko'paytmasini grafikning Laplasian matritsasining eigenval qiymati sifatida tenglashtiradi. Shuningdek, bu grafning xromatik polinomiyasining birinchi nolga teng bo'lmagan koeffitsientidir. Tutte teoremasida mukammal bir-biriga mos keladigan graflarni tavsiflovchi va grafik qattiqligini aniqlashda komponentlar soni muhim rol o'ynaydi.
Algoritmlar
Grafik tarkibiy qismlarini chiziqli vaqt ichida (grafikning uchlari va qirralari soni bo'yicha) kenglik yoki birinchi darajali qidirish yordamida hisoblash to'g'ri bo'ladi. Ikkala holatda ham, vertexning ma'lum bir v qismida boshlanadigan qidiruv v (va undan ko'prog'i yo'q) tarkibiy qismini qaytib kelishdan oldin topadi. Grafikning barcha tarkibiy qismlarini topish uchun, uning birinchi uchidan yoki chuqurligidan birinchi qidiruvni boshlab, pastadir avval topilgan tarkibiy qismga qo'shilmagan uchiga yetganda. Hopcroft & Tarjan (1973) mohiyatan ushbu algoritmni tavsiflaydi va shu paytda u "taniqli" bo'lganligini ta'kidlaydi.
Grafik tarkibiy qismlarini dinamik ravishda kuzatib borishning samarali algoritmlari mavjud, ular vertikal chiziqlar va qirralar qo'shilib, ajratilgan ma'lumotlar tuzilmalarini to'g'ridan-to'g'ri qo'llash sifatida mavjud. Ushbu algoritmlar har bir operatsiyaga amortizatsiya qilingan O (a (n)) vaqtni talab qiladi, bunda uchlari va qirralari qo'shilib, verteks tushadigan tarkibiy qism aniqlanadi, bu ikkala operatsiya, va a (n) juda tez o'sib boradigan teskari Ackermann funktsiyasi. Shu bilan bog'liq muammo tarkibiy qismlarni kuzatishdir, chunki barcha qirralar grafikadan ketma-ket o'chiriladi; Buni har bir so'rov uchun doimiy vaqt bilan hal qilish uchun algoritm va O (| V || E |) vaqt ma'lumotlarning tuzilishini saqlash vaqti; bu O (| V |) chetini o'chirish uchun amortizatsiya qilingan qiymat. O'rmonlar uchun narxni O (q + | V | log | V |) yoki O (log | V |) chetini o'chirish uchun amortizatsiya qilingan qiymatga kamaytirish mumkin (Shiloach & Even 1981).
Tadqiqotchilar hisoblashning yanada cheklangan modellarida tarkibiy qismlarni topish algoritmlarini, masalan, ishlaydigan xotirani logaritmik sonli bit bilan cheklangan dasturlar (L murakkabligi klassi bilan belgilanadi) bilan ham o'rganishgan. Lyuis va Papadimitriou (1982) loglar maydonida ikkita uchi yo'naltirilmagan grafikning bitta tarkibiy qismiga tegishli yoki yo'qligini sinab ko'rish mumkinmi, deb so'rashdi va ulanish uchun ekvivalent bo'lgan logspace ekvivalenti bo'lgan muammolarning murakkablik sinfini aniqladilar. Nihoyat Reingold (2008)
L = SL ekanligini ko'rsatib, logaritmik fazoda ushbu ulanish muammosini hal qilish uchun algoritm topishga muvaffaq bo'ldi.
Tasodifiy grafikadagi komponentlar
Tasodifiy grafiklarda komponentlarning o'lchamlari tasodifiy o'zgaruvchi tomonidan beriladi, bu esa o'z navbatida o'ziga xos modelga bog'liq.
G (n, p) modelida ko'rinishi turlicha bo'lgan uchta mintaqa mavjud:
Subkritik np <1: Barcha tarkibiy qismlar sodda va juda kichik, eng katta komponent
Tanqidiy
Superkritik np>1: qayerda tenglamaning ijobiy echimi. bu erda mos ravishda eng katta va ikkinchi o'rinda turadi. Qolgan barcha qismlarning o'lchamlari
Do'stlaringiz bilan baham: |
