{"entities":{"Q5893006":{"pageid":7931078,"ns":120,"title":"Item:Q5893006","lastrevid":93281645,"modified":"2026-06-05T04:08:08Z","type":"item","id":"Q5893006","labels":{"en":{"language":"en","value":"Non-separable and planar graphs."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2550901"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893006$5089B7C3-0F26-4833-BB3F-C908866E31D8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6b26b478a12c28972102aa8aa0164b9794e8ca61","datavalue":{"value":{"text":"Non-separable and planar graphs.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5893006$1C762472-D9B1-4FA2-A76B-05761DFB85A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"793783388e3d13b84f6f6b961b7761880bd38c6c","datavalue":{"value":"58.0608.01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893006$6815E775-D21C-4098-9C12-2B5B20407C11","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"983a5c73d000b856d30e0f17428a5b5b7d028b82","datavalue":{"value":"10.2307/1989545","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893006$38D41220-93B1-4CDB-994B-E3C4582A1431","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"df8563a34b35a91e952c14424ba2e926e2255a87","datavalue":{"value":{"entity-type":"item","numeric-id":559399,"id":"Q559399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893006$3DA2C408-513A-4B79-90EF-704B4E5F8FEA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7bbb53abe68aac0eeb25dacc2ea1a7274c90a69a","datavalue":{"value":{"time":"+1932-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5893006$8E185446-BB40-4C3B-9079-A69D1893D1E4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e93ffc70c9305ffdf9c39f1d54fda91104f17744","datavalue":{"value":"Diese Arbeit bildet die Grundlage einer Reihe weiterer Arbeiten des Verf. zur kombinatorischen Theorie der Graphen. Sie enth\u00e4lt in ihrem ersten Teil eine Untersuchung des Aufbaus von Graphen aus gewissen ``nicht-separablen'' Bestandteilen, wie sie sich \u00e4hnlich auch bei \\textit{D. K\u00f6nig} (1933; F. d. M. \\(59_{\\text{II}}\\), 1232, insbes. \\S 1 dieser Arbeit) findet. Der zweite Teil bringt eine interessante kombinatorische Charakterisierung derjenigen Graphen, die sich in die Ebene (oder die Kugelfl\u00e4che) einbetten lassen (``planare'' Graphen); inzwischen ist es Verf. gelungen, daraus die \\textit{Kuratowski}sche Kennzeichnung der nicht-planaren Graphen auf kombinatorischem Wege abzuleiten (\\textit{Kuratowski}, 1930; F. d. M. \\(56_{\\text{II}}\\), 1141; Verf., Fundamenta 21 (1933), 73-84; F. d. M. \\(59_{\\text{II}}\\), 1235).  Ein zusammenh\u00e4ngender Graph hei\u00dft nicht-separabel, wenn man ihn nicht aus zwei Graphen, deren jeder wenigstens eine Kante enth\u00e4lt, durch Verschmelzung eines Paares von Knotenpunkten entstanden denken kann; andernfalls hei\u00dft ein Graph (insbesondere auch jeder nicht-zusammenh\u00e4ngende Graph) separabel. Separabel ist z. B. jeder aus mehr als einer Kante bestehende Baum, nicht separabel ein Kreis (= einfach geschlossenes Polygon, ``circuit''). Man erh\u00e4lt eine eindeutig bestimmte Zerlegung eines Graphen in nicht-separable Bestandteile - ``Komponenten'' (bei \\textit{K\u00f6nig}: Glieder) -, wenn man jeden zusammenh\u00e4ngenden Bestandteil des Graphen in jedem etwa vorhandenen trennenden Knotenpunkt der oben angegebenen Art (``cut vertex'', bei \\textit{K\u00f6nig} und \\textit{Sainte Lagu\u00eb}: Artikulation) aufschneidet, wobei der trennende Knotenpunkt selbst in jeder der Komponenten, denen er angeh\u00f6rt, durch einen Knotenpunkt repr\u00e4sentiert wird. Jeder nicht-separable Teilgraph ist ganz in einer Komponente enthalten. Ein zusammenh\u00e4ngender separabler Graph ist aus seinen Komponenten nach Art einer Baumkurve aufgebaut, derart, da\u00df\\ je zwei Komponenten h\u00f6chstens einen Knotenpunkt gemeinsam haben uns es keinen Zyklus von Komponenten gibt, in dem je zwei benachbarte Komponenten einen Punkt gemeinsam haben. Versteht man unter dem Rang \\(R\\) eines Graphen die Zahl \\(V-P\\), \\(V\\)=Anzahl der Knotenpunkte, \\(P\\)=Anzahl der zusammenh\u00e4ngenden Bestandteile, unter der Nullit\u00e4t ( = erste \\textit{Betti}sche Zahl) die Zahl \\(E-R\\), \\(E=\\)Anzahl der Kanten, so sind Rang und Nullit\u00e4t eines Graphen gleich der Summe der R\u00e4nge bzw. Nullit\u00e4ten seiner Komponenten.  Die nicht-separablen Graphen sind dadurch gekennzeichnet, da\u00df\\ je zwei ihrer Ecken in einem Kreis enthalten sind (``zyklisch zusammenh\u00e4ngende'' Graphen); es ist also \\(N>0\\). \\(P=1, N=1\\) kennzeichnet die Kreise. Als Gegenst\u00fcck der Ranggleichung f\u00fcr separable Graphen hat man folgende Kennzeichnung der nicht-separablen: Verteilt man die Kanten des Graphen irgendwie auf zwei Teilgraphen, von denen jeder mindestens eine Kante enthalten soll, so gilt f\u00fcr die R\u00e4nge \\(R\\), \\(R_1\\), \\(R_2\\) der drei Graphen \\(R<R_1+R_2\\). Setzt man endlich viele nicht-separable Graphen durch Verschmelzen je eines Paares von Knotenpunkten zyklisch zusammen (wobei nat\u00fcrlich in jedem einzelnen Graphen zwei verschiedene Knotenpunkte mit denen der beiden Nachbarn zu identifizieren sind), so entsteht wieder ein nicht-separabler Graph. Jeder nicht separable Graph, der wenigstens zwei Kanten enth\u00e4lt, kann, ausgehend von einem Kreis, Schritt f\u00fcr Schritt in der Weise aufgebaut werden, da\u00df\\ man die Endpunkte einer neuen Kante oder eines neuen einfachen Kantenzuges mit zwei verschiedenen Knotenpunkten des schon vorhandenen Teiles identifiziert.  Zwei Graphen hei\u00dfen kongruent (in fr\u00fcheren Arbeiten des Verf: hom\u00f6omorph), wenn sich ihre Kanten und Knotenpunkte unter Erhaltung der Inzidenzen eineindeutig aufeinander beziehen lassen; sie hei\u00dfen \u00e4quivalent, wenn ihre Komponenten paarweise kongruent sind, abgesehen von vielleicht auftretenden isolierten Knotenpunkten. Ein Graph \\(G'\\) hei\u00dft zu einem Graphen \\(G\\) dual, wenn eine eineindeutige Zuordnung zwischen den Kanten von \\(G\\) und von \\(G'\\) besteht, die folgende Eigenschaft hat: Ist \\(H\\) ein Teilgraph von \\(G\\), \\(H'\\) derjenige Teilgraph von \\(G'\\), der aus allen und nur den Kanten von \\(G'\\) besteht, die nicht Bilder der Kanten von \\(H\\) sind, so gilt stets \\(R(H')=R(G')-N(H)\\) (\\(R\\)=Rang, \\(N\\)=Nullit\u00e4t). Dann ist auch \\(G\\) zu \\(G'\\) dual, und es gilt \\(R(G')=N(G)\\), \\(R(G)=N(G')\\). Die Dualit\u00e4tsbeziehung zwischen zwei Graphen wird weitgehend durch die zwischen den Komponenten bestimmt: Ist \\(G'\\) zu \\(G''\\) \u00e4quivalent, \\(G'\\) zu \\(G\\) dual, so ist auch \\(G''\\) zu \\(G\\) dual (aber ein Graph kann untereinander nicht \u00e4quivalente Duale haben). Sind die Komponenten von \\(G\\) und \\(G'\\) paarweise zueinander dual, so auch \\(G\\) und \\(G'\\). Sind die Kanten zweier Graphen \\(G\\) und \\(G'\\) eineindeutig so aufeinander bezogen, da\u00df\\ die Abbildung zugleich eine Abbildung zwischen den Paaren von Komponenten von \\(G\\) und \\(G'\\) ist, so sind \\(G\\) und \\(G'\\) dual. Umgekehrt: Bei der die Dualit\u00e4t vermittelnden Abbildung der Kanten entsprechen den Komponenten von \\(G\\) die Komponenten von \\(G'\\). Insbesondere ist ein zu einem nicht-separablen Graphen dualer Graph nicht-separabel.  Nicht jeder Graph besitzt einen Dualen. Es gilt vielmehr der Satz: Dann und nur Dann besitzt ein Graph einen Dualen, wenn er planar ist. Zum Beweis kann man sich offenbar auf nicht-separable Graphen beschr\u00e4nken, da sowohl die M\u00f6glichkeit der Einbettung in die Ebene als auch die Dualit\u00e4t nur von den einzelnen Komponenten abh\u00e4ngt. Zun\u00e4chst zeigt sich, da\u00df\\ beim \u00dcbergang von der durch einen Graphen bewirkten Zerlegung der Kugel zu der im \u00fcblichen Sinn der Mannigfaltigkeitstheorie dualen Zerlegung in der Tat ein im kombinatorischen Sinn dualer Graph entsteht. Umgekehrt zeigt ein Induktionsschlu\u00df, bei dem der schrittweise Aufbau der nicht-separablen Graphen benutzt wird, da\u00df\\ zwei im kombinatorischen Sinn duale Graphen sich so auf die Kugel legen lassen, da\u00df\\ sie zwei zueinander im \u00fcblichen Sinn duale Einteilungen der Kugel liefern. Aus der Existenz eines kombinatorisch Dualen zu einem planaren Graphen und der kombinatorischen Dualit\u00e4tsbedingung folgt nat\u00fcrlich die \\textit{Euler}sche Polyederformel. Als ersten Schritt in Richtung auf das \\textit{Kuratowski}sche Ergebnis zeigt Verf. noch: Keiner der beiden \\textit{Kuratowski}schen nicht-planaren Graphen besitzt einen Dualen.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5893006$38201513-1417-43A5-BCC6-2719517C34A4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"53782eb038bd5a2e6b186a8c36c714dccc04040f","datavalue":{"value":"2550901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893006$32D26678-FF54-4E54-AF0C-8F48650B9F16","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7240cdc8337f24f345a8b358b110241995abbc1b","datavalue":{"value":"Q30053175","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893006$054FE242-FEA8-4626-B071-4F9742D5326A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"144a6eebf639ea543bd03fa2e7064384b1e7bf2e","datavalue":{"value":{"entity-type":"item","numeric-id":593326,"id":"Q593326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893006$A31C8A6B-4DE3-4453-AC02-80827FCBC053","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893006$224D539A-6A1B-450E-90B1-D96DBD7BDB98","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d40b2901219592b36304e7f6b948feab36f77d90","datavalue":{"value":"https://doi.org/10.2307/1989545","type":"string"},"datatype":"url"},"type":"statement","id":"Q5893006$51574EB0-BC70-475F-BEAA-E9515B24428F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fb4630cec013826a834d10c248896226bf108c46","datavalue":{"value":"W4254149069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5893006$FC35C26A-E656-4FC8-A347-BC40E05DBDF6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d31ddd2a071b5cbac90da3e8f29d3f22b0ba0eba","datavalue":{"value":{"entity-type":"item","numeric-id":6480746,"id":"Q6480746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5893006$0D12F5E9-F56A-45B5-B563-AEC3FCC6470C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Non-separable and planar graphs.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Non-separable_and_planar_graphs."}}}}}