Cactus graph (original) (raw)
In der Graphentheorie bezeichnet ein Kaktusgraph (zum Teil auch nur Kaktus) einen zusammenhängenden Graphen, in dem sich jedes Paar seiner Kreise höchstens einen gemeinsamen Knoten teilt. Den Begriff Kaktusgraph (engl. cactus) führten Frank Harary und George Eugene Uhlenbeck ein. In dieser ursprünglichen Definition wurde jedoch verlangt, dass alle Kreise des Graphen Dreiecke sind.
| Property | Value |
|---|---|
| dbo:abstract | In der Graphentheorie bezeichnet ein Kaktusgraph (zum Teil auch nur Kaktus) einen zusammenhängenden Graphen, in dem sich jedes Paar seiner Kreise höchstens einen gemeinsamen Knoten teilt. Den Begriff Kaktusgraph (engl. cactus) führten Frank Harary und George Eugene Uhlenbeck ein. In dieser ursprünglichen Definition wurde jedoch verlangt, dass alle Kreise des Graphen Dreiecke sind. (de) In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or (for nontrivial cactus) in which every block (maximal subgraph without a cut-vertex) is an edge or a cycle. (en) En teoría de grafos, un cactus (a veces llamado árbol de cactus) es un grafo conectado en el que dos ciclos simples tienen como máximo un vértice en común. De manera equivalente, es un grafo conectado en el que cada arista pertenece a un ciclo simple como máximo, o (para cactus no triviales) en el que cada bloque (subgrafo máximo sin vértices de corte) es una arista o un ciclo. (es) En théorie des graphes, un graphe cactus (parfois appelé arbre cactus) est un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun. De manière équivalente, c'est un graphe connexe dans lequel chaque arête appartient à au plus un cycle simple, ou (pour les cactus non triviaux) dans lequel chaque bloc (sous-graphe maximal sans point d'articulation) est une arête ou un cycle. (fr) カクタスグラフ（もしくは単にカクタス、カクタス木）は任意の2つの単純閉路が2つ以上の共通頂点を持たない連結グラフである。別の言い方をすれば、全ての辺が高々1つの閉路にしか含まれない連結グラフや、（非自明だが）全ての（のない最大部分グラフ）が閉路または辺となる連結グラフであると言える。 (ja) В теории графов «кактус» (иногда используется название кактусовое дерево) — это связный граф, в котором любые два простых цикла имеют не более одной общей вершины. Эквивалентно, любое ребро в таком графе принадлежит максимум одному простому циклу. Эквивалентно (для нетривиального кактуса), любой блок (максимальный подграф без шарниров) является ребром или циклом. (ru) В теорії графів «кактус» (іноді використовується назва кактусове дерево) — це зв'язний граф, в якому будь-які два прості цикли мають не більше, ніж одну спільну вершину. Еквівалентно, будь-яке ребро в такому графі належить максимум одному простому циклу. Еквівалентно (для нетривіального кактуса), будь-який блок (максимальний підграф без шарнірів) є ребром або циклом. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Cactus_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.angelfire.com/electronic2/cas/ |
| dbo:wikiPageID | 9944209 (xsd:integer) |
| dbo:wikiPageLength | 13397 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1106080859 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_families dbr:Approximation_algorithm dbr:Cycle_(graph_theory) dbr:Kôdi_Husimi dbr:Pseudoforest dbc:Planar_graphs dbr:Complete_graph dbr:Connected_graph dbr:Matching_(graph_theory) dbr:Matroid_parity_problem dbr:Geographic_routing dbr:Electrical_circuit dbr:Frank_Harary dbr:Friendship_graph dbr:Glossary_of_graph_theory dbr:Graph_minor dbr:NP-hard dbr:Combinatorial_optimization dbr:Comparative_genomics dbr:Component_(graph_theory) dbr:Locally_linear_graph dbr:Outerplanar_graph dbr:Graceful_labeling dbr:Graph_embedding dbr:Graph_theory dbc:Integrated_circuits dbr:Block_graph dbr:Diamond_graph dbr:Planar_graph dbr:Greedy_embedding dbr:Polynomial_time dbr:Approximation_ratio dbr:George_Eugene_Uhlenbeck dbr:Vertex_(graph_theory) dbr:Euclidean_plane dbr:Facility_location_problem dbr:Planarization dbr:Polyhedral_graph dbr:Topological_graph_theory dbr:Downwardly_closed dbr:Forbidden_minor dbr:Plane_graph dbr:Cut-vertex dbr:File:Cactus_graph.svg dbr:File:Friendship_graphs.svg |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_families dbc:Planar_graphs dbc:Integrated_circuits |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | In der Graphentheorie bezeichnet ein Kaktusgraph (zum Teil auch nur Kaktus) einen zusammenhängenden Graphen, in dem sich jedes Paar seiner Kreise höchstens einen gemeinsamen Knoten teilt. Den Begriff Kaktusgraph (engl. cactus) führten Frank Harary und George Eugene Uhlenbeck ein. In dieser ursprünglichen Definition wurde jedoch verlangt, dass alle Kreise des Graphen Dreiecke sind. (de) In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or (for nontrivial cactus) in which every block (maximal subgraph without a cut-vertex) is an edge or a cycle. (en) En teoría de grafos, un cactus (a veces llamado árbol de cactus) es un grafo conectado en el que dos ciclos simples tienen como máximo un vértice en común. De manera equivalente, es un grafo conectado en el que cada arista pertenece a un ciclo simple como máximo, o (para cactus no triviales) en el que cada bloque (subgrafo máximo sin vértices de corte) es una arista o un ciclo. (es) En théorie des graphes, un graphe cactus (parfois appelé arbre cactus) est un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun. De manière équivalente, c'est un graphe connexe dans lequel chaque arête appartient à au plus un cycle simple, ou (pour les cactus non triviaux) dans lequel chaque bloc (sous-graphe maximal sans point d'articulation) est une arête ou un cycle. (fr) カクタスグラフ（もしくは単にカクタス、カクタス木）は任意の2つの単純閉路が2つ以上の共通頂点を持たない連結グラフである。別の言い方をすれば、全ての辺が高々1つの閉路にしか含まれない連結グラフや、（非自明だが）全ての（のない最大部分グラフ）が閉路または辺となる連結グラフであると言える。 (ja) В теории графов «кактус» (иногда используется название кактусовое дерево) — это связный граф, в котором любые два простых цикла имеют не более одной общей вершины. Эквивалентно, любое ребро в таком графе принадлежит максимум одному простому циклу. Эквивалентно (для нетривиального кактуса), любой блок (максимальный подграф без шарниров) является ребром или циклом. (ru) В теорії графів «кактус» (іноді використовується назва кактусове дерево) — це зв'язний граф, в якому будь-які два прості цикли мають не більше, ніж одну спільну вершину. Еквівалентно, будь-яке ребро в такому графі належить максимум одному простому циклу. Еквівалентно (для нетривіального кактуса), будь-який блок (максимальний підграф без шарнірів) є ребром або циклом. (uk) |
| rdfs:label | Kaktusgraph (de) Cactus graph (en) Grafo cactus (es) Graphe cactus (fr) カクタスグラフ (ja) Кактус (теория графов) (ru) Кактус (теорія графів) (uk) |
| owl:sameAs | freebase:Cactus graph yago-res:Cactus graph wikidata:Cactus graph dbpedia-de:Cactus graph dbpedia-es:Cactus graph dbpedia-fa:Cactus graph dbpedia-fr:Cactus graph dbpedia-hu:Cactus graph dbpedia-ja:Cactus graph dbpedia-ru:Cactus graph dbpedia-uk:Cactus graph https://global.dbpedia.org/id/f6E9 |
| prov:wasDerivedFrom | wikipedia-en:Cactus_graph?oldid=1106080859&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Friendship_graphs.svg wiki-commons:Special:FilePath/Cactus_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Cactus_graph |
| is dbo:wikiPageDisambiguates of | dbr:Cactus_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Triangular_cactus_graph |
| is dbo:wikiPageWikiLink of | dbr:Cycle_(graph_theory) dbr:Cycle_double_cover dbr:Unit_distance_graph dbr:Kôdi_Husimi dbr:Pseudoforest dbr:Robertson–Seymour_theorem dbr:Matroid_parity_problem dbr:Geodetic_graph dbr:Glossary_of_graph_theory dbr:Graph_coloring_game dbr:Hamiltonian_completion dbr:Treewidth dbr:Locally_linear_graph dbr:Forbidden_graph_characterization dbr:Outerplanar_graph dbr:Graceful_labeling dbr:Binary_matroid dbr:Block_graph dbr:Diamond_graph dbr:Greedy_coloring dbr:Greedy_embedding dbr:Metric_dimension_(graph_theory) dbr:Cactus_(disambiguation) dbr:Longest_path_problem dbr:Partial_k-tree dbr:Triangular_cactus_graph |
| is foaf:primaryTopic of | wikipedia-en:Cactus_graph |
