[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/kolorystyka-krawedzi-wykresu-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/kolorystyka-krawedzi-wykresu-wikipedia\/","headline":"Kolorystyka kraw\u0119dzi wykresu – Wikipedia","name":"Kolorystyka kraw\u0119dzi wykresu – Wikipedia","description":"before-content-x4 Artyku\u0142 w Wikipedii, Free L’Encyclop\u00e9i. after-content-x4 W teorii graf\u00f3w i algorytmice, a Kolorystyka kraw\u0119dzi wykresu polega na przypisywaniu koloru","datePublished":"2019-12-20","dateModified":"2019-12-20","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/0\/03\/Desargues_graph_3color_edge.svg\/220px-Desargues_graph_3color_edge.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/0\/03\/Desargues_graph_3color_edge.svg\/220px-Desargues_graph_3color_edge.svg.png","height":"220","width":"220"},"url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/kolorystyka-krawedzi-wykresu-wikipedia\/","wordCount":2475,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Artyku\u0142 w Wikipedii, Free L’Encyclop\u00e9i.         (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4W teorii graf\u00f3w i algorytmice, a Kolorystyka kraw\u0119dzi wykresu polega na przypisywaniu koloru ka\u017cdej kraw\u0119dzi, zapobiegaj\u0105cym dw\u00f3ch kraw\u0119dzi o wsp\u00f3lnym ko\u0144cu, aby mie\u0107 ten sam kolor. Figurka przeciwna jest przyk\u0142adem prawid\u0142owego zabarwienia kraw\u0119dzi. Rzeczywi\u015bcie jest weryfikowane, \u017ce \u017caden szczyt nie jest wsp\u00f3lny dla dw\u00f3ch kraw\u0119dzi tego samego koloru. Nale\u017cy zauwa\u017cy\u0107, \u017ce tutaj nie by\u0142oby mo\u017cliwe zabarwienie kraw\u0119dzi wykresu tylko dwoma kolorami.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4  Wspomniane bez dodatkowych wyja\u015bnie\u0144, wyra\u017cenie \u201ekolorowanie kraw\u0119dzi wykresu\u201d wyznacza fakt przypisywania ka\u017cdemu kraw\u0119dziowi koloru, tak \u017ce dwie s\u0105siednie kraw\u0119dzie (to znaczy posiadanie wsp\u00f3lnego ko\u0144ca) i nigdy nie mia\u0142y tego samego koloru. (Jest to podw\u00f3jne poj\u0119cie kolorowania szczyt\u00f3w wykresu.) Minimalna liczba kolor\u00f3w wymaganych do pokolorowania kraw\u0119dzi wykresu G jest nazywany indeks chromatyczny z G Lub Chromatyczna liczba kraw\u0119dzi z G i odnotowano \u03c7 \u2032 ( G ), a czasem \u03c7 Pierwszy ( G ). Nie nale\u017cy go myli\u0107 z liczb\u0105 chromatyczn\u0105 (szczytami) G , zauwa\u017cono \u03c7 ( G ). Si d ( G ) to maksymalny stopie\u0144 G i \u03bc ( G ) Jego mnogo\u015b\u0107 (maksymalna liczba kraw\u0119dzi na pert pik\u00f3w), nast\u0119pnie:        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Klasyfikacja wykres\u00f3w i okre\u015blenie ich liczby chromatycznej [[[ modyfikator |. Modyfikator i kod ] Jak wspomniano powy\u017cej, \u03c7 \u2032 ( G ) jest zawsze r\u00f3wny \u03b4 ( G ) lub \u00e0 \u03b4 ( G ) + 1. G Klasa 1 jest powiedziana w pierwszym przypadku i klasie 2 w drugim. W 1981 roku Holyer udowodni\u0142 [[[ Pierwszy ] To, \u017ce okre\u015blenie przynale\u017cno\u015bci prostego wykresu do jednej lub drugiej z tych dw\u00f3ch klas jest problemem NP. Jednak w niekt\u00f3rych szczeg\u00f3lnych przypadkach istniej\u0105 zasady, kt\u00f3re pozwalaj\u0105 szybko zako\u0144czy\u0107. Na przyk\u0142ad, zwr\u00f3cone [[[ 2 ] \u017be prosty wykres maksymalnego stopnia stopnia co najmniej 8, jest zawsze klasy 1 i przypuszcza\u0142, \u017ce tak samo dla maksymalnego stopnia r\u00f3wnego 6 lub 7 (znamy proste wykresy stopnia p\u0142askie maksymalnie 2, 3, 4 lub 5 i klasa 2). Sanders (W) et Zhao [[[ 3 ] wykazali przypadek \u03b4 ( G ) = 7 do przypuszczenia. Ta domniemanie znajduje zastosowanie w ca\u0142kowitej kolorystyce (W) . Kolorowanie kraw\u0119dzi kompletnych wykres\u00f3w mo\u017ce by\u0107 u\u017cyte do zaprogramowania turnieju okr\u0105g\u0142ego w jak najmniejszych rundach, tak aby ka\u017cda para konkurent\u00f3w staru si\u0119 starci w jednej z rund. W tej aplikacji szczyty wykresu odpowiadaj\u0105 konkurentom turnieju, kraw\u0119dzie odpowiadaj\u0105 gier, a kolory kraw\u0119dzi odpowiadaj\u0105 rundom [[[ 4 ] . Kolejn\u0105 aplikacj\u0105 mo\u017ce by\u0107 planowanie produkcji zestawu obiekt\u00f3w z ograniczeniem, \u017ce ka\u017cde zadanie produkcyjne musi by\u0107 wykonywane na konkretnym komputerze, uniemo\u017cliwiaj\u0105c jednocze\u015bnie wykonanie tego samego maszyny. Je\u015bli wszystkie zadania maj\u0105 taki sam czas trwania, problem ten mo\u017cna sformalizowa\u0107 jako kolorowanie dwustronnego multigrafu, w kt\u00f3rym szczyty po jednej stronie dwustronnej reprezentuj\u0105 obiekty, kt\u00f3re maj\u0105 by\u0107 wyprodukowane, szczyty po drugiej stronie dwustronnej reprezentuj\u0105 Maszyny produkcyjne, kraw\u0119dzie reprezentuj\u0105 zadania do wykonania, a kolory reprezentuj\u0105 odst\u0119py czasu, w kt\u00f3rych mo\u017cna wykona\u0107 ka\u017cde zadanie [[[ 5 ] . \u2191 (W) Ian Holyer, ‘ NP kompletno\u015b\u0107 koloru kraw\u0119dzi \u00bb W SIAM J. Obliczanie. W tom. dziesi\u0119\u0107, N O 4, 1981 W P. 718-720 (Doi 10.1137\/0210055) .  \u2191 (ru) V. G. Vising, \u00abKrytyczne wykresy z dan\u0105 klas\u0105 chromatyczn\u0105\u00bb, Disk Metody. Analiz. , tom. 5, 1965, P. 9-17 .  \u2191 (W) Daniel P. Sanders i Yue Zhao, ‘ Planarne wykresy maksymalnego stopnia siedem to klasa I \u00bb W J. Combin. Teoria ser. B W tom. 83, N O 2, 2001 W P. 201-212 (Doi 10.1006\/jctb.2001.2047) .  \u2191 I. Burke , D. tkania i J. Kingston W \u00ab5.6.5 Harmonogram sportowy\u00bb , w J. L. Gross i J. Yellen (wydawcy), Podr\u0119cznik teorii graf\u00f3w , CRC Press, 2004 , 1192 P.  (ISBN 978-1-58488-090-5 W Czytaj online ) W P. 462  \u2191 D. P. Williamson , The. Hala , J. A. Hoogeveen , C. A. J. Hurkens , J. K. Lenstra , S. V. Sevast’janov i D. B. Shmoys \u00ab Kr\u00f3tkie harmonogramy sklepu \u00bb, Badania operacyjne W tom. 45, 1997 W P. 288\u2013294 (Doi 10.1287\/opre.45.2.288, Jstor 171745, Recenzje matematyczne 1644998)  (W) Tommy R. Jensen a Bjarne toft, Problemy z kolorowaniem wykresu , John Wiley & Sons, 2011 ( Pierwszy Odno\u015bnie  wyd. 1995), 320 P.  (ISBN 978-1-118-03074-5 W Czytaj online ) (z) D\u00e9nes k\u0151nig, ‘ O wykresach i ich zastosowaniu w celu ustalenia teorii i teorii ilo\u015bciowej \u00bb W Anna\u0142y matematyczne W tom. 77, N O 4, 1916 W P. 453-465 (Doi 10.1007 \/ BF01456961 W Czytaj online  [[[ Archive Du 19 stycznia 2015 ] , skonsultua\u0142em si\u0119 z 30 wrze\u015bnia 2013 )        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/kolorystyka-krawedzi-wykresu-wikipedia\/#breadcrumbitem","name":"Kolorystyka kraw\u0119dzi wykresu – Wikipedia"}}]}]