This HTML5 document contains 17 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n5http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
n12https://web.archive.org/web/20161130183820/http:/compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/
xsdhhttp://www.w3.org/2001/XMLSchema#
n7http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Kritikus_gráf
rdfs:label
Kritikus gráf
dct:subject
n7:Gráfcsaládok n7:Gráfok_színezése
dbo:wikiPageID
1440190
dbo:wikiPageRevisionID
22013223
dbo:wikiPageExternalLink
n12:Chap%207.PDF
prop-hu:wikiPageUsesTemplate
n5:Harvtxt n5:Harvnb n5:Mvar n5:Fordítás n5:Citation n5:Harv
dbo:abstract
A kritikusság általánosságban bármilyen tulajdonságra vagy mértékre utalhat. A gráfelmélet területén a kifejezést szinte mindig egy gráf kromatikus számával kapcsolatban használjuk.A kritikus gráfok érdekességét az adja, hogy a gráfelméletileg fontos tulajdonság, a kromatikus szám szempontjából minimálisak.Precízebben: Egy G gráf csúcsa vagy éle a gráf kritikus eleme, ha törlésével G kromatikus száma csökkenne.Nyilvánvalóan a csökkenés legfeljebb 1-gyel történhet. Egy kritikus gráf olyan gráf, melynek minden csúcsa vagy éle kritikus elem.Egy k-kritikus gráf olyan kritikus gráf, aminek kromatikus száma k; ha egy k kromatikus számú G gráf minden csúcsa kritikus elem, akkor a gráf k-csúcskritikus, ha pedig egy k élkromatikus számú (kromatikus indexű) gráf minden éle kritikus elem, akkor a gráf k-élkritikus. Az n csúccsal és m éllel rendelkező k-kritikus G gráfok néhány tulajdonsága: * G egyetlen komponensből áll. * G véges (ez a de Bruijn–Erdős-tétel: ). * δ(G) ≥ k − 1, tehát minden csúcs legalább k − 1 csúccsal szomszédos. Ami ennél erősebb G (k − 1)-szeresen élösszefüggő. Lásd * Ha G (k − 1)-reguláris, tehát minden csúcs pontosan k − 1 csúccsal szomszédos, akkor G vagy a Kk vagy egy páratlan kör. Ez a Brooks-tétel; lásd ). * 2 m ≥ (k − 1) n + k − 3 . * 2 m ≥ (k − 1) n + [(k − 3)/(k2 − 3)] n . * G vagy felbontható két kisebb kritikus gráfra, ahol minden csúcsot a másik részgráf minden csúcsával él köti össze, vagy G-nek legalább 2k − 1 csúcsa van . Ennél erősebb állítás is igaz: G vagy felbontható az előbbi módon, vagy G minden v csúcsához tartozik olyan k-színezés, amiben v színe nem szerepel más csúcsnál, minden más színosztályba pedig legalább két csúcs tartozik . Könnyen belátható, hogy G pontosan akkor csúcskritikus, ha minden v csúcsához tartozik egy optimális, jó színezése, melyben v egyelemű színosztály. alapján minden k-kritikus gráf előállítható a Kk teljes gráfból a és a két nem szomszédos csúcs azonosításának művelete segítségével. Az így megalkotott gráfok jó színezéséhez mindig legalább k színre van szükség. Egy kétszeresen kritikus gráf vagy duplakritikus gráf (double-critical graph) olyan összefüggő gráf, melyben bármely két szomszédos csúcs törlése a kromatikus számot kettővel csökkenti.Nyitott kérdés, hogy a Kk teljes gráfon kívül létezik-e más duplakritikus k-kromatikus számú gráf .
prov:wasDerivedFrom
wikipedia-hu:Kritikus_gráf?oldid=22013223&ns=0
dbo:wikiPageLength
6457
foaf:isPrimaryTopicOf
wikipedia-hu:Kritikus_gráf
Subject Item
wikipedia-hu:Kritikus_gráf
foaf:primaryTopic
dbpedia-hu:Kritikus_gráf