Bridge (graph theory) (original) (raw)
En grafeteorio, ponto estas eĝo tia, ke forigi ĝin multigas . Ekvivalente, eĝo estas ponto se kaj nur se ĝi ne apartenas al iu ajn ciklo. Grafeo estas senponta se ĝi enhavas neniun ponton.
| Property | Value |
|---|---|
| dbo:abstract | En grafeteorio, ponto estas eĝo tia, ke forigi ĝin multigas . Ekvivalente, eĝo estas ponto se kaj nur se ĝi ne apartenas al iu ajn ciklo. Grafeo estas senponta se ĝi enhavas neniun ponton. (eo) In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges. This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see Glossary of graph theory terms § bridge. (en) En teoría de grafos, una arista de corte, puente o istmo es una arista que al ser eliminada en un grafo incrementa el número de componentes conexas de este. Equivalentemente, una arista es un puente si y sólo si no está contenida en ningún ciclo. El concepto de arista de corte se puede generalizar a un conjunto de aristas. Así, un corte de aristas-l o corte de líneas-l es un conjunto de l aristas que si se quitan, desconectan el grafo. Por lo tanto, una arista de corte es un corte de aristas-1. Análogamente, un vértice de corte o punto de corte, es un vértice que al eliminarse incrementa el número de componentes conexos del grafo. La conectividad de un grafo se puede calcular en términos del número de aristas o vértices de corte que posee. Esta conectividad es una medida de su cohesión o robustez. Un importante problema abierto que involucra puentes es la conjetura del ciclo de doble cobertura, propuesta por Seymour y Szekeres (1978 y 1979, independientemente), que establece que todo grafo sin puentes admite un conjunto de ciclos que contiene cada arista exactamente dos veces. (es) En théorie des graphes, un isthme ou un pont est une arête d'un graphe dont l'élimination induit un graphe avec plus de composantes connexes que le graphe initial. De façon équivalente, une arête est un isthme si et seulement si elle n'est pas contenue dans un cycle. (fr) Nella teoria dei grafi, un ponte (conosciuto anche come bridge, cut-edge, cut arc o istmo) è un arco la cui eliminazione aumenta il numero di componenti connesse. Equivalentemente, un arco è un ponte se e solo se non è contenuto in nessun ciclo. Un grafo senza ponti è equivalente a un grafo con per ogni componente non banale. Un ponte può essere individuato anche tramite l'analisi della matrice di connessione. (it) Most – krawędź grafu spójnego, której usunięcie z grafu rozspójnia go.Według innej definicji mostem jest krawędź, której usunięcie zwiększa liczbę spójnych składowych grafu. (pl) Em teoria dos grafos, uma ponte (também conhecida como aresta-de-corte ou arco de corte ou um istmo) é uma aresta cuja deleção em um grafo aumenta o número de deste. Equivalentemente, uma aresta é uma ponte, se e somente se ela não está contida em qualquer ciclo. Um grafo é dito ser sem ponte se ele não contém pontes. É fácil ver que isso é equivalente a de cada componente não trivial. (pt) 在圖論中，一條邊被稱為「橋」代表這條邊一旦被刪除，這張圖的連通塊數量會增加。 等價地說，一條邊是一座橋若且唯若這條邊不在任何環上。一張圖可以有零或多座橋。 (zh) Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле. (ru) В теорії графів, міст — ребро, видалення якого збільшує кількість компонент зв'язності (або, інакше кажучі, відокремлює підграф). Рівнозначне визначення, ребро є мостом тоді і тільки тоді, коли вони не є частиною будь-якого циклу. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Graph_cut_edges.svg?width=300 |
| dbo:wikiPageID | 1305071 (xsd:integer) |
| dbo:wikiPageLength | 9551 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1060337471 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Robert_Tarjan dbr:Biconnected_component dbc:Graph_connectivity dbr:Paul_Seymour_(mathematician) dbr:Cubic_graph dbr:Cycle_(graph_theory) dbr:Depth-first_search dbr:Ear_decomposition dbr:George_Szekeres dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Linear_time dbr:Tree_(graph_theory) dbr:Tree_traversal dbr:Cycle_double_cover_conjecture dbr:K-edge-connected_graph dbr:K-vertex-connected_graph dbr:Cut_(graph_theory) dbr:Equivalence_relation dbr:Graph_theory dbr:Connected_component_(graph_theory) dbr:Strong_orientation dbr:Forest_(graph_theory) dbr:Spanning_forest dbr:Robbins'_theorem dbr:Chain_decomposition dbr:Articulation_vertex dbr:Cut_vertex dbr:File:Graph_cut_edges.svg dbr:File:Undirected.svg |
| dbp:wikiPageUsesTemplate | dbt:Authority_control dbt:Reflist dbt:Short_description dbt:Slink |
| dcterms:subject | dbc:Graph_connectivity |
| gold:hypernym | dbr:Edge |
| rdf:type | owl:Thing dbo:Agent |
| rdfs:comment | En grafeteorio, ponto estas eĝo tia, ke forigi ĝin multigas . Ekvivalente, eĝo estas ponto se kaj nur se ĝi ne apartenas al iu ajn ciklo. Grafeo estas senponta se ĝi enhavas neniun ponton. (eo) In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges. This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see Glossary of graph theory terms § bridge. (en) En théorie des graphes, un isthme ou un pont est une arête d'un graphe dont l'élimination induit un graphe avec plus de composantes connexes que le graphe initial. De façon équivalente, une arête est un isthme si et seulement si elle n'est pas contenue dans un cycle. (fr) Nella teoria dei grafi, un ponte (conosciuto anche come bridge, cut-edge, cut arc o istmo) è un arco la cui eliminazione aumenta il numero di componenti connesse. Equivalentemente, un arco è un ponte se e solo se non è contenuto in nessun ciclo. Un grafo senza ponti è equivalente a un grafo con per ogni componente non banale. Un ponte può essere individuato anche tramite l'analisi della matrice di connessione. (it) Most – krawędź grafu spójnego, której usunięcie z grafu rozspójnia go.Według innej definicji mostem jest krawędź, której usunięcie zwiększa liczbę spójnych składowych grafu. (pl) Em teoria dos grafos, uma ponte (também conhecida como aresta-de-corte ou arco de corte ou um istmo) é uma aresta cuja deleção em um grafo aumenta o número de deste. Equivalentemente, uma aresta é uma ponte, se e somente se ela não está contida em qualquer ciclo. Um grafo é dito ser sem ponte se ele não contém pontes. É fácil ver que isso é equivalente a de cada componente não trivial. (pt) 在圖論中，一條邊被稱為「橋」代表這條邊一旦被刪除，這張圖的連通塊數量會增加。 等價地說，一條邊是一座橋若且唯若這條邊不在任何環上。一張圖可以有零或多座橋。 (zh) Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле. (ru) В теорії графів, міст — ребро, видалення якого збільшує кількість компонент зв'язності (або, інакше кажучі, відокремлює підграф). Рівнозначне визначення, ребро є мостом тоді і тільки тоді, коли вони не є частиною будь-якого циклу. (uk) En teoría de grafos, una arista de corte, puente o istmo es una arista que al ser eliminada en un grafo incrementa el número de componentes conexas de este. Equivalentemente, una arista es un puente si y sólo si no está contenida en ningún ciclo. El concepto de arista de corte se puede generalizar a un conjunto de aristas. Así, un corte de aristas-l o corte de líneas-l es un conjunto de l aristas que si se quitan, desconectan el grafo. Por lo tanto, una arista de corte es un corte de aristas-1. (es) |
| rdfs:label | Brücke (Graphentheorie) (de) Ponto (grafeteorio) (eo) Bridge (graph theory) (en) Arista de corte (es) Isthme (théorie des graphes) (fr) Ponte (teoria dei grafi) (it) Most (teoria grafów) (pl) Ponte (teoria dos grafos) (pt) Мост (теория графов) (ru) Міст (теорія графів) (uk) 桥 (图论) (zh) |
| owl:sameAs | freebase:Bridge (graph theory) wikidata:Bridge (graph theory) dbpedia-de:Bridge (graph theory) dbpedia-eo:Bridge (graph theory) dbpedia-es:Bridge (graph theory) dbpedia-fa:Bridge (graph theory) dbpedia-fr:Bridge (graph theory) dbpedia-hu:Bridge (graph theory) dbpedia-it:Bridge (graph theory) dbpedia-pl:Bridge (graph theory) dbpedia-pt:Bridge (graph theory) dbpedia-ro:Bridge (graph theory) dbpedia-ru:Bridge (graph theory) dbpedia-sk:Bridge (graph theory) dbpedia-sl:Bridge (graph theory) dbpedia-uk:Bridge (graph theory) http://ur.dbpedia.org/resource/پل_(نظریہ_گراف) dbpedia-zh:Bridge (graph theory) https://global.dbpedia.org/id/2PTj2 |
| prov:wasDerivedFrom | wikipedia-en:Bridge_(graph_theory)?oldid=1060337471&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Undirected.svg wiki-commons:Special:FilePath/Graph_cut_edges.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Bridge_(graph_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Bridge_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Bridge_(graph) dbr:Bridgeless_graph dbr:Cut-edge dbr:Cut_arc dbr:Cut_edge |
| is dbo:wikiPageWikiLink of | dbr:Michael_D._Plummer dbr:Nowhere-zero_flow dbr:Biconnected_component dbr:Apollonian_network dbr:Cubic_graph dbr:Cycle_double_cover dbr:Depth-first_search dbr:Isthmus_(disambiguation) dbr:Connectivity_(graph_theory) dbr:Nash-Williams_theorem dbr:Orientation_(graph_theory) dbr:Social_network_analysis dbr:Petersen_graph dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Graph_minor dbr:Sauer–Shelah_lemma dbr:Line_graph dbr:Skew-symmetric_graph dbr:Snark_(graph_theory) dbr:Split_(graph_theory) dbr:Well-covered_graph dbr:K-edge-connected_graph dbr:Lollipop_graph dbr:Cut_(graph_theory) dbr:Daniel_Kráľ dbr:Dual_graph dbr:Edge_coloring dbr:Eulerian_path dbr:Bridge_(interpersonal) dbr:Edge_cycle_cover dbr:Watkins_snark dbr:Planar_graph dbr:Grid_bracing dbr:Bridge_(disambiguation) dbr:Tutte_polynomial dbr:Strong_orientation dbr:Factor-critical_graph dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Rigidity_matroid dbr:Robbins'_theorem dbr:Tarjan's_algorithm dbr:Tadpole_graph dbr:Bridge_(graph) dbr:Bridgeless_graph dbr:Cut-edge dbr:Cut_arc dbr:Cut_edge |
| is foaf:primaryTopic of | wikipedia-en:Bridge_(graph_theory) |
