Split graph (original) (raw)
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 .
| Property | Value |
|---|---|
| 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 | wiki-commons:Special:FilePath/Split_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.emis.de/journals/JIS/VOL3/ROYLE/royle.pdf http://mi.mathnet.ru/eng/mz3413 https://archive.org/details/graphclassessurv0000bran |
| dbo:wikiPageID | 9928681 (xsd:integer) |
| dbo:wikiPageLength | 14817 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096691155 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Annals_of_Mathematics dbc:Graph_families dbc:Perfect_graphs dbr:Path_graph dbr:Degree_sequence dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:One-to-one_correspondence dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:Martin_Charles_Golumbic dbr:Clique_(graph_theory) dbr:Combinatorica dbr:Comparability_graph dbr:Perfect_graph dbr:Almost_all dbr:Cycle_graph dbr:Discrete_Mathematics_(journal) dbr:Graph_enumeration dbr:Graph_partition dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Intersection_graph dbr:Interval_graph dbr:Chordal_graph dbc:Intersection_classes_of_graphs dbr:Cocoloring dbr:Cograph dbr:Threshold_graph dbr:Splittance dbr:Doklady_Akademii_Nauk_SSSR dbr:Neighborhood_(graph_theory) dbr:Canadian_Journal_of_Mathematics dbr:Vertex_(graph_theory) dbr:European_Journal_of_Combinatorics dbr:Strongly_chordal_graph dbr:Maximal_clique dbr:Permutation_graph dbr:Skew-merged_permutation dbr:Maximum_independent_set dbr:Strong_Perfect_Graph_Theorem dbr:Hamiltonian_cycle dbr:Forbidden_induced_subgraph dbr:Complement_(graph_theory) dbr:Star_graph dbr:Sperner_families dbr:File:Split_graph.svg |
| dbp:author1Link | Regina Tyshkevich (en) |
| dbp:author2Link | Peter Ladislaw Hammer (en) |
| dbp:last | Hammer (en) Földes (en) Chernyak (en) Tyshkevich (en) |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Citation dbt:Doi dbt:Harvtxt dbt:Math dbt:Mvar dbt:OEIS dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sub dbt:Harvs |
| dbp:year | 1977 (xsd:integer) 1979 (xsd:integer) |
| dcterms:subject | dbc:Graph_families dbc:Perfect_graphs dbc:Intersection_classes_of_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Communication100033020 yago:Graph107000195 yago:Group100031264 yago:WikicatIntersectionClassesOfGraphs yago:VisualCommunication106873252 yago:WikicatPerfectGraphs |
| 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 | freebase:Split graph yago-res:Split graph wikidata:Split graph dbpedia-eo:Split graph dbpedia-fa:Split graph dbpedia-fr:Split graph dbpedia-hu:Split graph dbpedia-ru:Split graph dbpedia-uk:Split graph https://global.dbpedia.org/id/3c5Rr |
| prov:wasDerivedFrom | wikipedia-en:Split_graph?oldid=1096691155&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Split_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Split_graph |
| is dbo:wikiPageRedirects of | dbr:Double_split_graph dbr:Join_decomposition |
| is dbo:wikiPageWikiLink of | dbr:Dense_subgraph dbr:András_Hajnal dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Regina_Tyshkevich dbr:Intersection_number_(graph_theory) dbr:Radio_coloring dbr:Glossary_of_graph_theory dbr:Equitable_coloring dbr:Chordal_bipartite_graph dbr:Clique_(graph_theory) dbr:Complement_graph dbr:Perfect_graph dbr:Forbidden_graph_characterization dbr:Graph_isomorphism_problem dbr:Graph_sandwich_problem dbr:Kalai's_3^d_conjecture dbr:Interval_graph dbr:Chordal_graph dbr:Bipartite_graph dbr:Cocoloring dbr:Threshold_graph dbr:Dominating_set dbr:Book_(graph_theory) dbr:Bull_graph dbr:Splittance dbr:Metric_dimension_(graph_theory) dbr:Longest_path_problem dbr:Neighbor-net dbr:Strong_perfect_graph_theorem dbr:Strongly_chordal_graph dbr:Universal_vertex dbr:SplitsTree dbr:Skew-merged_permutation dbr:Word-representable_graph dbr:Double_split_graph dbr:Join_decomposition |
| is foaf:primaryTopic of | wikipedia-en:Split_graph |
