This HTML5 document contains 32 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/
n9https://books.google.com/
dbpedia-huhttp://hu.dbpedia.org/resource/
n10http://portal.acm.org/
prop-huhttp://hu.dbpedia.org/property/
n14http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n6http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n7http://www.cs.sunysb.edu/~algorith/files/
n15http://www.renyi.hu/~p_erdos/
n4http://gdz.sub.uni-goettingen.de/
n17http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Élszínezés
rdfs:label
Élszínezés
dct:subject
n17:Gráfok_színezése
dbo:wikiPageID
1545561
dbo:wikiPageRevisionID
21984910
dbo:wikiPageExternalLink
n4:index.php%3Fid=11&PPN=PPN235181684_0077&DMDID=DMDLOG_0051&L=1 n7:edge-coloring.shtml n9:books%3Fid=mKkIGIea_BkC&pg=PA462 n10:citation.cfm%3Fid=1873601.1873605 n14:invitedpaper2.pdf n15:1977-20.pdf
prop-hu:wikiPageUsesTemplate
n6:Refend n6:Mvar n6:Wd n6:Math n6:Wayback n6:Citation n6:Fordítás n6:Sfnp n6:Harv n6:Refbegin n6:Harvtxt n6:Reflist n6:Fő
prop-hu:date
20150119200819
prop-hu:url
n4:index.php%3Fid=11&PPN=PPN235181684_0077&DMDID=DMDLOG_0051&L=1
dbo:abstract
A matematika, azon belül a gráfelmélet területén egy gráf élszínezése során színeket rendelnek hozzá a gráf éleihez. Általában jó élszínezésekkel foglalkoznak, melyek során az ugyanabból a csúcsból kiinduló élek mindig különböző színűek. Például a jobb oldali ábrán látható élszínezés három színt (piros, kék, zöld) használ. Az élszínezés a gráfok lehetséges színezéseinek csak egyetlen típusa. Az élszínezési probléma azt vizsgálja, hogy jól színezhetők-e adott gráf élei legfeljebb k különböző színnel, adott k-ra, illetve a lehető legkevesebb szín felhasználásával. Az adott gráf éleihez szükséges minimális színek számát a gráf élkromatikus számának vagy kromatikus indexének nevezik. Az illusztráción látható gráf élei kiszínezhetők három színnel, de kettővel nem, ezért a gráf élkromatikus száma három. A Vizing-tétel értelmében az egyszerű gráf élszínezéséhez szükséges színek száma vagy a maximális fokszáma, Δ vagy Δ+1. Egyes gráfok esetében, mint a páros gráfok vagy magas fokszámú síkbarajzolható gráfok, a kromatikus index mindig Δ, multigráfok esetén pedig akár 3Δ/2 is lehet. Léteznek polinom idejű algoritmusok páros gráfok optimális színezésének, illetve nem páros egyszerű gráfok legfeljebb Δ+1-színezésének előállítására; az optimális élszínezés általános esetben azonban feladat és a legjobb ismert algoritmusok is exponenciális idejűek. Az élszínezési problémának számos olyan változatát tanulmányozták, ahol a színek hozzárendelésekor a szomszédosság elkerülése mellett egyéb feltételeknek is teljesülniük kell. Az élszínezések gyakorlati szerepet kapnak az ütemezési problémákban és az optikai hálózatok frekvenciakiosztásában.
prov:wasDerivedFrom
wikipedia-hu:Élszínezés?oldid=21984910&ns=0
dbo:wikiPageLength
62899
foaf:isPrimaryTopicOf
wikipedia-hu:Élszínezés
Subject Item
dbpedia-hu:Kromatikus_index
dbo:wikiPageRedirects
dbpedia-hu:Élszínezés
Subject Item
dbpedia-hu:Élkromatikus_szám
dbo:wikiPageRedirects
dbpedia-hu:Élszínezés
Subject Item
wikipedia-hu:Élszínezés
foaf:primaryTopic
dbpedia-hu:Élszínezés