Robbins' theorem (original) (raw)
Der Satz von Robbins (nach Herbert Robbins) ist ein Satz aus der Graphentheorie der einen Zusammenhang zwischen dem Kantenzusammenhang eines ungerichteten Graphen und der Möglichkeit die Kanten so zu orientieren, dass ein stark zusammenhängender gerichteter Graph entsteht herstellt. Der Satz besagt, dass die Kanten eines zusammenhängender ungerichteten Graphen genau dann so orientiert werden können, dass der entstehende gerichtete Graph stark zusammenhängend ist wenn der ursprüngliche Graph 2-fach kantenzusammenhängend ist (keine Brücken enthält).
| Property | Value |
|---|---|
| dbo:abstract | Der Satz von Robbins (nach Herbert Robbins) ist ein Satz aus der Graphentheorie der einen Zusammenhang zwischen dem Kantenzusammenhang eines ungerichteten Graphen und der Möglichkeit die Kanten so zu orientieren, dass ein stark zusammenhängender gerichteter Graph entsteht herstellt. Der Satz besagt, dass die Kanten eines zusammenhängender ungerichteten Graphen genau dann so orientiert werden können, dass der entstehende gerichtete Graph stark zusammenhängend ist wenn der ursprüngliche Graph 2-fach kantenzusammenhängend ist (keine Brücken enthält). (de) El teorema de Robbins, nombrado en honor al matemático estadounidense que lo estableció en 1939, dice: en donde la condición Riemann de super-integrabilidad establece: (es) In graph theory, Robbins' theorem, named after Herbert Robbins, states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge. (en) En théorie des graphes, le théorème de Robbins, nommé d'après Herbert Robbins qui l'a formulé en 1939, dit que les graphes qui possèdent une orientation forte sont exactement les graphes connexes sans isthme ou graphes 2-arête-connexes. (fr) Na teoria dos grafos, a Teoria de Robbins, denominada em referência a Herbert Robbins (1939), diz que os grafos que tem uma forte orientação são os grafos de . Isto é, a possibilidade de escolher uma direção para cada aresta de um grafo não direcionado G, transformando-o em um grafo orientado que é um caminho de qualquer vértice para qualquer outro vértice, se e somente se G é conectado e não tem ponte (teoria dos grafos). (pt) Теоре́ма Ро́ббінса, названа на честь американського математика Герберта Роббінса, стверджує, що графи, які мають сильні орієнтації — це точно 2-реберно-зв'язні графи. Тобто тоді й лише тоді можна вибрати напрямок кожного ребра неорієнтованого графа G, перетворивши граф на орієнтований граф, у якому існує (орієнтований) шлях з будь-якої вершини в будь-яку іншу вершину, коли граф G зв'язний і не має мостів. (uk) Теорема Роббинса, названная по имени американского математика Герберта Роббинса, утверждает, что графы, имеющие сильные ориентации, — это в точности рёберно 2-связные графы. То есть тогда и только тогда можно выбрать направление каждого ребра неориентированного графа G, превратив граф в ориентированный граф, в котором существует (ориентированный) путь из любой вершины в любую другу вершину, когда граф G связен и не имеет мостов. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Ear_decomposition.png?width=300 |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=EYAwztXnzf8C&pg=PA7 https://books.google.com/books%3Fid=pOBXUoVZ9EEC&pg=PA135 https://books.google.com/books%3Fid=vLRNRebXuKYC&pg=PA254 https://docs.lib.purdue.edu/cgi/viewcontent.cgi%3Farticle=1361&context=cstech https://books.google.com/books%3Fid=unEloQ_sYmkC&pg=PA498 |
| dbo:wikiPageID | 36633800 (xsd:integer) |
| dbo:wikiPageLength | 9357 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116543116 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_connectivity dbr:Undirected_graph dbr:Depth-first_search dbr:Ear_decomposition dbr:Information_Processing_Letters dbr:Connected_graph dbr:Mixed_graph dbr:Cross_bracing dbr:Linear_time dbr:Communications_of_the_ACM dbr:K-edge-connected_graph dbr:American_Mathematical_Monthly dbr:Bridge_(graph_theory) dbr:Directed_graph dbr:Graph_theory dbr:Structural_rigidity dbc:Theorems_in_graph_theory dbr:The_American_Mathematical_Monthly dbr:Greedy_algorithm dbr:Grid_bracing dbr:Strong_orientation dbr:Parallel_computer dbr:File:Ear_decomposition.png |
| dbp:authorlink | Herbert Robbins (en) |
| dbp:first | Herbert (en) |
| dbp:last | Robbins (en) |
| dbp:wikiPageUsesTemplate | dbt:Otheruses4 dbt:Citation dbt:Harvtxt dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Harvs |
| dbp:year | 1939 (xsd:integer) |
| dct:subject | dbc:Graph_connectivity dbc:Theorems_in_graph_theory |
| rdf:type | yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Der Satz von Robbins (nach Herbert Robbins) ist ein Satz aus der Graphentheorie der einen Zusammenhang zwischen dem Kantenzusammenhang eines ungerichteten Graphen und der Möglichkeit die Kanten so zu orientieren, dass ein stark zusammenhängender gerichteter Graph entsteht herstellt. Der Satz besagt, dass die Kanten eines zusammenhängender ungerichteten Graphen genau dann so orientiert werden können, dass der entstehende gerichtete Graph stark zusammenhängend ist wenn der ursprüngliche Graph 2-fach kantenzusammenhängend ist (keine Brücken enthält). (de) El teorema de Robbins, nombrado en honor al matemático estadounidense que lo estableció en 1939, dice: en donde la condición Riemann de super-integrabilidad establece: (es) In graph theory, Robbins' theorem, named after Herbert Robbins, states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge. (en) En théorie des graphes, le théorème de Robbins, nommé d'après Herbert Robbins qui l'a formulé en 1939, dit que les graphes qui possèdent une orientation forte sont exactement les graphes connexes sans isthme ou graphes 2-arête-connexes. (fr) Na teoria dos grafos, a Teoria de Robbins, denominada em referência a Herbert Robbins (1939), diz que os grafos que tem uma forte orientação são os grafos de . Isto é, a possibilidade de escolher uma direção para cada aresta de um grafo não direcionado G, transformando-o em um grafo orientado que é um caminho de qualquer vértice para qualquer outro vértice, se e somente se G é conectado e não tem ponte (teoria dos grafos). (pt) Теоре́ма Ро́ббінса, названа на честь американського математика Герберта Роббінса, стверджує, що графи, які мають сильні орієнтації — це точно 2-реберно-зв'язні графи. Тобто тоді й лише тоді можна вибрати напрямок кожного ребра неорієнтованого графа G, перетворивши граф на орієнтований граф, у якому існує (орієнтований) шлях з будь-якої вершини в будь-яку іншу вершину, коли граф G зв'язний і не має мостів. (uk) Теорема Роббинса, названная по имени американского математика Герберта Роббинса, утверждает, что графы, имеющие сильные ориентации, — это в точности рёберно 2-связные графы. То есть тогда и только тогда можно выбрать направление каждого ребра неориентированного графа G, превратив граф в ориентированный граф, в котором существует (ориентированный) путь из любой вершины в любую другу вершину, когда граф G связен и не имеет мостов. (ru) |
| rdfs:label | Satz von Robbins (de) Teorema de Robbins (es) Théorème de Robbins (fr) Robbins' theorem (en) Teorema de Robbins (pt) Теорема Роббинса (ru) Теорема Роббінса (uk) |
| owl:sameAs | freebase:Robbins' theorem yago-res:Robbins' theorem wikidata:Robbins' theorem dbpedia-de:Robbins' theorem dbpedia-es:Robbins' theorem dbpedia-fr:Robbins' theorem dbpedia-pt:Robbins' theorem dbpedia-ru:Robbins' theorem dbpedia-uk:Robbins' theorem https://global.dbpedia.org/id/4uB95 |
| prov:wasDerivedFrom | wikipedia-en:Robbins'_theorem?oldid=1116543116&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Ear_decomposition.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Robbins'_theorem |
| is dbo:wikiPageRedirects of | dbr:Robbins_theorem |
| is dbo:wikiPageWikiLink of | dbr:Nowhere-zero_flow dbr:Orientation_(graph_theory) dbr:K-edge-connected_graph dbr:Bridge_(graph_theory) dbr:Strongly_connected_component dbr:Grid_bracing dbr:Strong_orientation dbr:Robbins_theorem |
| is foaf:primaryTopic of | wikipedia-en:Robbins'_theorem |
