Biconnected graph (original) (raw)
数学のグラフ理論における2重連結グラフ（2じゅうれんけつグラフ、英: biconnected graph）とは、任意の頂点が取り除かれても連結であるという意味で「分離不可能」なグラフのことを言う。したがって、2重連結グラフにはは存在しない。 2-連結であるという性質は、2重連結性と基本的に同値である。ただし、二つの頂点からなる完全グラフはしばしば、2重連結であるが2-連結ではないと見なされることに注意されたい。 この性質は特に、一つの辺（あるいは、接続）を取り除く際の非連結を防ぐための、グラフの2重冗長性を維持する上で有用である。 この冗長性に関する性質により、2重連結グラフは、ネットワークの分野（フローネットワークを参照されたい）において非常に重要となる。
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices. The property of being 2-connected is equivalent to biconnectivity, except that the complete graph of two vertices is usually not regarded as 2-connected. This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection). The use of biconnected graphs is very important in the field of networking (see Network flow), because of this property of redundancy. (en) 数学のグラフ理論における2重連結グラフ（2じゅうれんけつグラフ、英: biconnected graph）とは、任意の頂点が取り除かれても連結であるという意味で「分離不可能」なグラフのことを言う。したがって、2重連結グラフにはは存在しない。 2-連結であるという性質は、2重連結性と基本的に同値である。ただし、二つの頂点からなる完全グラフはしばしば、2重連結であるが2-連結ではないと見なされることに注意されたい。 この性質は特に、一つの辺（あるいは、接続）を取り除く際の非連結を防ぐための、グラフの2重冗長性を維持する上で有用である。 この冗長性に関する性質により、2重連結グラフは、ネットワークの分野（フローネットワークを参照されたい）において非常に重要となる。 (ja) В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности. Теорема Уитни утверждает, в частности, что граф двусвязен тогда и только тогда, когда между любыми двумя его вершинами есть минимум два непересекающихся пути. Таким образом, двусвязный граф не имеет шарниров. Это свойство особенно полезно при рассмотрении графов с двойным резервированием, чтобы избежать разрыва при удалении единственного ребра. Использование двусвязных графов очень важно в области сетей (смотри транспортные сети) ввиду их свойств резервирования. (ru) У теорії графів двозв'язний граф — це зв'язний і неподільний граф, в тому сенсі, що видалення будь-якої вершини не призведе до втрати зв'язності. Таким чином, двозв'язний граф не має шарнірів. Властивість вершинної 2-зв'язності еквівалентна двозв'язності графу з одним винятком — повний граф з двома вершинами іноді вважається двозв'язним, але не вершинно-двозв'язним. Ця властивість особливо корисна при розгляді графів з подвійним резервуванням, щоб уникнути розриву при видаленні єдиного ребра. Використання двозв'язних графів дуже важливо в області мереж (дивись потокова мережа), зважаючи на притаманну їм властивість резервування. (uk) 在图论中，一个点双连通图是一个连通且“不可分离”的图，意思是如果任何一个顶点被去除，图仍是连通的。所以这样一个双连通图就没有。的性质和点双连通是几乎等价的，除了一条边连接两个点构成的图，它是点双连通的，但不是2-点连通的。 这个性质在维护一个有2度冗余的图中特别有用，为了防止去除一条边（或连接）之后的不连通。 由于冗余的这种特性，双连通图的使用在网络领域非常重要（参见网络流）。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/5_Node_Not-Biconnected.svg?width=300 |
| dbo:wikiPageExternalLink | http://mathworld.wolfram.com/BiconnectedGraph.html https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html https://code.google.com/p/jbpt/ |
| dbo:wikiPageID | 4989397 (xsd:integer) |
| dbo:wikiPageLength | 3035 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123654962 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Biconnected_component dbc:Graph_connectivity dbc:Graph_families dbr:Undirected_graph dbr:Complete_graph dbr:Graph_(discrete_mathematics) dbr:K-vertex-connected_graph dbr:Edge_(graph_theory) dbr:Flow_network dbr:Directed_graph dbr:Graph_theory dbr:Redundancy_(engineering) dbr:Vertex_(graph_theory) dbr:Articulation_vertex |
| dbp:wikiPageUsesTemplate | dbt:Short_description dbt:Graph_connectivity_sidebar |
| dct:subject | dbc:Graph_connectivity dbc:Graph_families |
| rdf:type | yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | 数学のグラフ理論における2重連結グラフ（2じゅうれんけつグラフ、英: biconnected graph）とは、任意の頂点が取り除かれても連結であるという意味で「分離不可能」なグラフのことを言う。したがって、2重連結グラフにはは存在しない。 2-連結であるという性質は、2重連結性と基本的に同値である。ただし、二つの頂点からなる完全グラフはしばしば、2重連結であるが2-連結ではないと見なされることに注意されたい。 この性質は特に、一つの辺（あるいは、接続）を取り除く際の非連結を防ぐための、グラフの2重冗長性を維持する上で有用である。 この冗長性に関する性質により、2重連結グラフは、ネットワークの分野（フローネットワークを参照されたい）において非常に重要となる。 (ja) 在图论中，一个点双连通图是一个连通且“不可分离”的图，意思是如果任何一个顶点被去除，图仍是连通的。所以这样一个双连通图就没有。的性质和点双连通是几乎等价的，除了一条边连接两个点构成的图，它是点双连通的，但不是2-点连通的。 这个性质在维护一个有2度冗余的图中特别有用，为了防止去除一条边（或连接）之后的不连通。 由于冗余的这种特性，双连通图的使用在网络领域非常重要（参见网络流）。 (zh) In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices. The property of being 2-connected is equivalent to biconnectivity, except that the complete graph of two vertices is usually not regarded as 2-connected. This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection). (en) В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности. Теорема Уитни утверждает, в частности, что граф двусвязен тогда и только тогда, когда между любыми двумя его вершинами есть минимум два непересекающихся пути. Таким образом, двусвязный граф не имеет шарниров. Это свойство особенно полезно при рассмотрении графов с двойным резервированием, чтобы избежать разрыва при удалении единственного ребра. (ru) У теорії графів двозв'язний граф — це зв'язний і неподільний граф, в тому сенсі, що видалення будь-якої вершини не призведе до втрати зв'язності. Таким чином, двозв'язний граф не має шарнірів. Властивість вершинної 2-зв'язності еквівалентна двозв'язності графу з одним винятком — повний граф з двома вершинами іноді вважається двозв'язним, але не вершинно-двозв'язним. (uk) |
| rdfs:label | Biconnected graph (en) 2重連結グラフ (ja) Двусвязный граф (ru) 双连通图 (zh) Двозв'язний граф (uk) |
| owl:sameAs | freebase:Biconnected graph yago-res:Biconnected graph wikidata:Biconnected graph dbpedia-fa:Biconnected graph dbpedia-hu:Biconnected graph dbpedia-ja:Biconnected graph dbpedia-ru:Biconnected graph dbpedia-uk:Biconnected graph dbpedia-zh:Biconnected graph https://global.dbpedia.org/id/44ZM2 |
| prov:wasDerivedFrom | wikipedia-en:Biconnected_graph?oldid=1123654962&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/4_Node_Biconnected.svg wiki-commons:Special:FilePath/4_Node_Not-Biconnected.svg wiki-commons:Special:FilePath/5_Node_Biconnected.svg wiki-commons:Special:FilePath/5_Node_Not-Biconnected.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Biconnected_graph |
| is dbo:wikiPageRedirects of | dbr:Bi-connected_graph |
| is dbo:wikiPageWikiLink of | dbr:Queen's_graph dbr:Biconnected_component dbr:Cycle_double_cover dbr:Unit_distance_graph dbr:Depth-first_search dbr:Pebble_motion_problems dbr:15_puzzle dbr:Connectivity_(graph_theory) dbr:178_(number) dbr:Planar_separator_theorem dbr:Cyclic_graph dbr:K-vertex-connected_graph dbr:Dual_graph dbr:Edge_coloring dbr:Brooks'_theorem dbr:Outerplanar_graph dbr:Hamiltonian_path dbr:Bipolar_orientation dbr:SPQR_tree dbr:Explicit_multi-threading dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Prism_graph dbr:Simultaneous_embedding dbr:Bi-connected_graph |
| is dbp:properties of | dbr:Queen's_graph |
| is foaf:primaryTopic of | wikipedia-en:Biconnected_graph |
