Biconnected grafiği - Biconnected graph
Olarak grafik teorisi , bir biconnected grafiktir bağlı ve "olarak ayrılamayan" bir grafiktir herhangi birine halinde, yani tepe kaldırılacak olan, grafik bağlı kalır. Bu nedenle, bir biconnected grafik, sahip mafsal köşe .
Olma özelliği 2-bağlantılı olduğu uyarı ile, biconnectivity eşdeğerdir tam grafik biconnected iki köşe bazen kabul edilir, fakat 2-bağlı değil.
Bu özellik, iki kat içeren bir grafik muhafaza özellikle yararlıdır artıklık tek çıkartılması üzerine bağlantı kesilmesini önlemek için kenar (veya bağlantı).
Kullanımı biconnected grafikleri (bkz ağ alanında çok önemli Ağ akışını artıklık nedeniyle bu özelliğin,).
içindekiler
Tanım
Bir biconnected yönsüz grafik tek bir tepe silme (ve olay kenarlar) tarafından kesilen parçaya kırık olmayan bir bağlı grafiktir.
Bir biconnected yönlendirilmiş grafik bir şekilde gerçekleştirilir ki, herhangi iki köşe için v ve w iki yönlendirilmiş yol vardır v için ağırlık daha fazla ortak diğer hiçbir köşe sahip v ve w .
Tepe Noktaları | Olasılıklar sayısı |
---|---|
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 |
Örnekler
Ayrıca bakınız
Referanslar
- Eric W. Weisstein. "Biconnected Grafik." MathWorld'den-Wolfram Web Resource itibaren. http://mathworld.wolfram.com/BiconnectedGraph.html
- Algoritma Sözlük ve Veri Yapıları [Online] Paul E. Siyah, "biconnected grafik", Paul E. Siyah, ed., Standartlar ve Teknoloji ABD Ulusal Enstitüsü. 17 Aralık 2004 (erişilen TODAY) Satıcı: https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html
Dış bağlantılar
- Biconnected bileşenler Java uygulamasının ağaç jBPT kütüphanesinde (BCTree sınıfına bakın).