{"entities":{"Q567002":{"pageid":568769,"ns":120,"title":"Item:Q567002","lastrevid":62946639,"modified":"2026-04-11T09:09:54Z","type":"item","id":"Q567002","labels":{"en":{"language":"en","value":"Congruent graphs and the connectivity of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2550902"}},"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":"Q567002$6D851073-DD85-4544-8699-A4F157CEB6BA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f89c520ff53f48f26d361a0bf38ae3364d5b3f6b","datavalue":{"value":{"text":"Congruent graphs and the connectivity of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q567002$90750539-4D0A-4E1A-B884-EAD8E59371B8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8da4fa57c622cef84f211f35e9226936ab4cf4d3","datavalue":{"value":"58.0609.01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q567002$920A4AA3-52D5-4885-B5CA-77AB88A70D2F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"56b0234c07260e8a0c0fa0d008126c0a543c693a","datavalue":{"value":"10.2307/2371086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q567002$640C2B5A-B179-43A5-BAB5-5F99243AF654","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1add02162fef49a66552187e850c2369475498a6","datavalue":{"value":{"entity-type":"item","numeric-id":559377,"id":"Q559377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q567002$9413935C-D83F-4852-AF79-0FEB16D7BD13","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":"Q567002$65AFE4AF-9592-4078-9311-A015AC65AEDC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"988aa10adab8f2d4425c8e8029929b1dcb1181fd","datavalue":{"value":"Verf. betrachtet zun\u00e4chst Graphen, in denen keine Schlingen auftreten und keine zwei Knotenpunkte durch mehr als eine Kante verbunden sind. Wenn zwischen den Kannten zweier solcher Graphen eine eineindeutige Zuordnung besteht, bei der zwei Kanten des einen Graphen dann und nur dann einen Knotenpunkt gemeinsam haben, wenn dasselbe f\u00fcr die entsprechenden Kanten des anderen gilt, so zeigt ein triviales Beispiel, da\u00df\\ zwei solche Graphen nicht notwendig kongruent, d. h. ihre Ecken und Kanten eineindeutig unter Erhaltung der Inzidenzbeziehnung aufeinander bezogen sind: Der aus drei Kanten mit genau einem gemeinsamen Knotenpunkt bestehende Graph ist dem aus den Ecken und Seiten eines Dreiecks bestehenden Graphen nicht kongruent. Das ist aber - so zeigt Verf. - der einzige Ausnahmefall: Wenn keiner der beiden Graphen der aus drei Kanten mit einer gemeinsamen Ecke bestehende Graph ist, so folgt aus dem Bestehen einer Kantenzuordung von der oben erw\u00e4hnten Art die Kongruenz der beiden Graphen.  Weitere Aussagen \u00e4hnlicher Art kann man f\u00fcr dreifach zusammenh\u00e4ngende Graphen machen. Ein zusammenh\u00e4ngender Graph mit wenigstens \\(n+1\\) Knotenpunkten hei\u00dft \\(n\\)-fach zusammenh\u00e4ngend, wenn es nicht m\u00f6glich ist, aus ihm \\(n-1\\) oder weniger Knotenpunkte samt den in ihnen endenden Kanten wegzulassen, derart da\u00df\\^^Mder entstehende Graph nicht mehr zusammenh\u00e4ngend ist, ein Graph, der \\(n\\)-fach, aber nicht \\((n+1)\\)-fach zusammenh\u00e4ngend ist, hat die Zusammenhangszahl (``connectivity'') \\(n\\). Es wird bewiesen: Wenn zwischen den Kanten zweier dreifach zusammenh\u00e4ngender Graphen eine eineindeutige Zuordnung besteht, bei der Kreise oder auch Teilgraphen der Nullit\u00e4t 1 einander entsprechen, so sind die beiden Graphen einander kongruent.  \u00dcber die Struktur der \\(n\\)-fach zusammenh\u00e4ngenden Graphen (in denen jetzt zwei Ecken auch durch mehrere Kanten verbunden sein d\u00fcrfen) werden folgende Aussagen gemacht: Dann und nur dann ist ein Graph \\(n\\)-fach zusammenh\u00e4ngend, wenn mann ihn f\u00fcr kein \\(k<n\\) aus zwei mehr als \\(k\\) Knotenpunkte enthaltenden Graphen durch Identifikation von \\(k\\) Knotenpunkten aufbauen kann. Ein Graph mit mindestens zwei Knotenpunkten, der durch Tilgen von weniger als \\(n\\) Kanten zerlegt werden kann, ist nicht \\(n\\)-fach zusammenh\u00e4ngend. L\u00e4\u00dft man aus einem \\(n\\)-fach zusammenh\u00e4ngenden Graphen einen Knotenpunkt und die in ihm endenden Kanten weg, so entsteht ein \\((n-1)\\)-fach zusammenh\u00e4ngender Graph. Dann und nur dann ist ein Graph, in dem zwei Knotenpunkte durch h\u00f6chstens eine Kante verbunden sind, \\(n\\)-fach zusammenh\u00e4ngend, wenn je zwei Knotenpunkte durch \\(n\\) bis auf die gemeinsamen Endpunkte paarweise (kanten- und knotenpunkt- )fremde Kantenz\u00fcge verbunden werden k\u00f6nnen (vgl. hierzu \\textit{Menger}, Fundamenta 10 (1926), 96-115; F. d. M. 53, 561 (JFM 53.0561.*); \\textit{N. Rutt}, 1929; F. d. M. \\(55_{\\text{I}}\\), 330; ferner \\textit{D. K\u00f6nig}, 1933; F. d. M. \\(59_{\\text{II}}\\), 1232).  Bei der Untersuchung dualer Graphen (siehe vorstehendes Referat) l\u00e4\u00dft man zweckm\u00e4\u00dfigerweise auch Graphen mit Schlingen und mehreren Verbindungen desselben Knotenpunktpaares zu. Zwischen den Zusammenhangseigenschaften zweier zusammenh\u00e4ngender zueinander dualer Graphen besteht folgende Beziehung: \\(G\\) sei nicht-separabel und zerfalle, wenn man die Ecken \\(a_1, a_2, \\dots, a_n\\) mit den in ihnen endenden Kanten tilgt, in zwei Bestandteile \\(H_1\\) und \\(H_2\\), w\u00e4hrend keine echte Teilmenge der \\(a_i\\) mit den zugeh\u00f6rigen Kanten \\(G\\) zerlegt. Die Nullit\u00e4t von \\(H_1\\) sei positiv, oder wenigstens ein \\(a_i\\) sei mit \\(H_1\\) durch wenigstens zwei Kanten verbunden; entsprechend f\u00fcr \\(H_2\\). Wenn dann \\(G'\\) zu \\(G\\) dual ist, so kann \\(G'\\) durch Tilgen einer den \\(a_i\\) in bestimmter Weise zugeordneten Menge von \\(n\\) Kanten zerlegt werden. F\u00fcr dreifach zusammenh\u00e4ngende Graphen ohne Schlingen und ohne mehrfache Verbindungen von Knotenpunktpaaren liefert dieser Satz: Jeder dazu duale Graph ist ebenfalls dreifach zusammenh\u00e4ngend, und - in Verbindung mit einem der obigen Kongruenzs\u00e4tze -: Der duale Graph ist in diesem Fall eindeutig bestimmt.","type":"string"},"datatype":"string"},"type":"statement","id":"Q567002$151B024A-B26A-4794-8651-4860482E12FE","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":"Q567002$DCC594C1-E995-4A74-9ACC-D65923A0A470","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"750e97583de33ea43e43e3b33230f5eb9246f5be","datavalue":{"value":"2550902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q567002$B9015919-94C5-4CE5-8A6C-D7C1C9033DBD","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"953917b923591275b9ffaae2dc71f0b65f469f75","datavalue":{"value":"Q55872301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q567002$F31FEBAE-7293-41B2-BAFC-04EDB45CDFF0","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":"Q567002$42A8085B-08CD-4873-B0FE-539B4F9B3DC8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"95c7db2a961f029a5d3008d8a2cf917c18c48468","datavalue":{"value":"https://doi.org/10.2307/2371086","type":"string"},"datatype":"url"},"type":"statement","id":"Q567002$B8156B3F-EC7E-4F23-8D64-318D00D3229D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a60b74a1021da95f501ebee94f32368651268edc","datavalue":{"value":"W4231597948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q567002$B6EED26C-7847-4DBE-9335-EE316282D252","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":"Q567002$5F6E6A75-C551-47FD-AAB3-A9F3AD56E2CD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Congruent graphs and the connectivity of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Congruent_graphs_and_the_connectivity_of_graphs"}}}}}