| dbo:abstract
|
- En grafeteorio, fenda grafeo estas grafeo en kiu la verticoj povas esti disdividitaj en klikon kaj . La dispartigo en klikon kaj sendependan aron ne nepre estas unika; ekzemple, la vojo a-b-c estas fenda grafeo, verticoj de kiu povas esti disdividitaj en tri malsamaj manieroj:
* kliko {a, b} kaj la sendependa aro {c}
* kliko {b, c} kaj la sendependa aro {a}
* kliko {b} kaj la sendependa aro {a, c} Fendaj grafeoj povas esti karakterigitaj per iliaj , grafeo estas fenda se kaj nur se neniu konkludita subgrafeo estas ciklo sur kvar aŭ kvin verticoj, aŭ paro de disaj lateroj (la komplemento de 4-ciklo). Fendaj grafeoj estis unue studitaj de Földes kaj Hammer en du paperoj en 1977, kaj sendepende prezentitaj de Tiŝkeviĉ kaj Ĉernjak en 1979. (eo)
- En théorie des graphes, un graphe scindé ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977, et introduit indépendamment par Tyshkevich et Tchernyak en 1979 . (fr)
- In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer , and independently introduced by Tyshkevich and Chernyak. A split graph may have more than one partition into a clique and an independent set; for instance, the path a–b–c is a split graph, the vertices of which can be partitioned in three different ways: 1.
* the clique {a, b} and the independent set {c} 2.
* the clique {b, c} and the independent set {a} 3.
* the clique {b} and the independent set {a, c} Split graphs can be characterized in terms of their forbidden induced subgraphs: a graph is split if and only if no induced subgraph is a cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle). (en)
- В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество. Расщепляемые графы впервые изучали Фёлдес и Хаммер, и независимо ввели Тышкевич и Черняк. Расщепляемый граф может иметь несколько разложений на клику и независимое множество. Так, путь a-b-c является расщепляемым и может быть разбит тремя разными способами: 1.
* клика {a,b} и независимое множество {c} 2.
* клика {b,c} и независимое множество {a} 3.
* клика {b} и независимое множество {a,c} Расщепляемые графы можно охарактеризовать в терминах их запрещённых подграфов — граф расщепляем в том и только в том случае, когда никакой порождённый подграф не является циклом с четырьмя или пятью вершинами, а также нет пары несвязных вершин (то есть дополнения цикла из 4 вершин). (ru)
- У теорії графів розщеплюваним графом називають граф, у якому вершини можна розділити на кліку і незалежну множину. Розщеплювані графи вперше вивчали Фелдес і Гаммер, і незалежно ввели Тишкевич і Черняк. Розщеплюваний граф може мати кілька розкладів на кліку та незалежну множину. Так, шлях a-b-c є розщеплюваним і його можна розбити трьома різними способами: 1.
* кліка {a,b} і незалежна множина {c} 2.
* кліка {b,c} і незалежне безліч {a} 3.
* кліка {b} і незалежне безліч {a,c} Розщеплювані графи можна охарактеризувати в термінах заборонених підграфів — граф розщеплюваний тоді й лише тоді, коли жодний породжений підграф не є циклом з чотирма або п'ятьма вершинами, а також немає пари незв'язних вершин (тобто доповнення циклу з 4 вершин). (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 14817 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:author1Link
| |
| dbp:author2Link
|
- Peter Ladislaw Hammer (en)
|
| dbp:last
|
- Hammer (en)
- Földes (en)
- Chernyak (en)
- Tyshkevich (en)
|
| dbp:wikiPageUsesTemplate
| |
| dbp:year
|
- 1977 (xsd:integer)
- 1979 (xsd:integer)
|
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En théorie des graphes, un graphe scindé ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977, et introduit indépendamment par Tyshkevich et Tchernyak en 1979 . (fr)
- En grafeteorio, fenda grafeo estas grafeo en kiu la verticoj povas esti disdividitaj en klikon kaj . La dispartigo en klikon kaj sendependan aron ne nepre estas unika; ekzemple, la vojo a-b-c estas fenda grafeo, verticoj de kiu povas esti disdividitaj en tri malsamaj manieroj:
* kliko {a, b} kaj la sendependa aro {c}
* kliko {b, c} kaj la sendependa aro {a}
* kliko {b} kaj la sendependa aro {a, c} Fendaj grafeoj estis unue studitaj de Földes kaj Hammer en du paperoj en 1977, kaj sendepende prezentitaj de Tiŝkeviĉ kaj Ĉernjak en 1979. (eo)
- In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer , and independently introduced by Tyshkevich and Chernyak. A split graph may have more than one partition into a clique and an independent set; for instance, the path a–b–c is a split graph, the vertices of which can be partitioned in three different ways: (en)
- В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество. Расщепляемые графы впервые изучали Фёлдес и Хаммер, и независимо ввели Тышкевич и Черняк. Расщепляемый граф может иметь несколько разложений на клику и независимое множество. Так, путь a-b-c является расщепляемым и может быть разбит тремя разными способами: 1.
* клика {a,b} и независимое множество {c} 2.
* клика {b,c} и независимое множество {a} 3.
* клика {b} и независимое множество {a,c} (ru)
- У теорії графів розщеплюваним графом називають граф, у якому вершини можна розділити на кліку і незалежну множину. Розщеплювані графи вперше вивчали Фелдес і Гаммер, і незалежно ввели Тишкевич і Черняк. Розщеплюваний граф може мати кілька розкладів на кліку та незалежну множину. Так, шлях a-b-c є розщеплюваним і його можна розбити трьома різними способами: 1.
* кліка {a,b} і незалежна множина {c} 2.
* кліка {b,c} і незалежне безліч {a} 3.
* кліка {b} і незалежне безліч {a,c} (uk)
|
| rdfs:label
|
- Fenda grafeo (eo)
- Graphe scindé (fr)
- Split graph (en)
- Расщепляемый граф (ru)
- Розщеплюваний граф (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
