Coloració de grafs: diferència entre les revisions
Pàgina nova, amb el contingut: «thumb|right|Una coloració adequada del [[graf de Petersen amb 3 colors, el mínim nombre possible perquè no n'hi hag...». |
(Cap diferència)
|
Revisió del 20:56, 8 abr 2015
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/220px-Petersen_graph_3-coloring.svg.png)
En teoria de grafs, la coloració de grafs és un cas especial d'etiquetatge de grafs, una assignació d'etiquetes tradicionalment anomenades «colors» als elements d'un graf subjecte a certes restriccions. En la seva forma més senzilla, és una manera d'acolorir els vèrtexs d'un graf de tal manera que no n'hi hagi dos de contigus del mateix color; d'això se'n diu coloració de vèrtexs. Similarment, la coloració d'arestes consisteix en assignar un color a cada aresta tal que no n'hi hagi dues d'adjacents del mateix color i la coloració de cares d'un graf planar consisteix en assignar un color a cada cara o regió tal que no hi hagi dues cares del mateix color amb un costat en comú.
El punt de partida del tema és la coloració de vèrtexs, ja que la resta de problemes de coloració es poden reduir a una de vèrtexs. Per exemple, la coloració d'arestes d'un graf és tan sols una coloració de vèrtexs del seu graf línia i la coloració de cares d'un graf pla és simplement una coloració de vèrtexs del seu dual. Tanmateix, els problemes que no són de coloració de vèrtexs solen estudiar-se tal i com són. Això és per una part per la perspectiva i per l'altra perquè certs problemes són més fàcils d'estudiar amb un sistema diferent —la coloració d'arestes n'és un exemple.
La convenció d'utilitzar colors prové de la cartografia, on els països o regions s'acoloreixen diferent per distingir-se. Aquest sistema es generalitzà acolorint les cares d'un graf incrustat en el pla. Per dualitat planar esdevingué coloració de vèrtexs i d'aquesta forma es generalitza a tots els grafs. En les representacions matemàtiques i computacionals, és habitual usar els primers enters positius o no negatius com a «colors». Més generalment, es pot usar qualsevol conjunt finit com a «conjunt de colors».
La coloració de grafs té diverses utilitats pràctiques així com reptes teòrics. Apart dels tipus clàssics de problemes, també es poden aplicar diferents limitacions al graf, a l'assignació del color o fins i tot al color en si. Entre el públic general ha assolit popularitat a través del trencaclosques numèric sudoku. La coloració de grafs segueix sent un camp actiu de recerca.
Fonts
- Barenboim, L. & Elkin, M. (2009), "Distributed (Δ + 1)-coloring in linear (in Δ) time", Proceedings of the 41st Symposium on Theory of Computing, pàg. 111–120, ISBN 978-1-60558-506-2, DOI 10.1145/1536414.1536432
- Panconesi, A. & Srinivasan, A. (1996), "On the complexity of distributed network decomposition", Journal of Algorithms, vol. 20
- Schneider, J. (2010), "A new technique for distributed symmetry breaking", Proceedings of the Symposium on Principles of Distributed Computing
- Schneider, J. (2008), "A log-star distributed maximal independent set algorithm for growth-bounded graphs", Proceedings of the Symposium on Principles of Distributed Computing
- Beigel, R. & Eppstein, D. (2005), "3-coloring in time O(1.3289n)", Journal of Algorithms 54 (2)): 168–204, DOI 10.1016/j.jalgor.2004.06.008
- Björklund, A.; Husfeldt, T. & Koivisto, M. (2009), "Set partitioning via inclusion–exclusion", SIAM Journal on Computing 39 (2): 546–563, DOI 10.1137/070683933
- Brélaz, D. (1979), "New methods to color the vertices of a graph", Communications of the ACM 22 (4): 251–256, DOI 10.1145/359094.359101
- Brooks, R. L. & Tutte, W. T. (1941), "On colouring the nodes of a network", Proceedings of the Cambridge Philosophical Society 37 (2): 194–197, DOI 10.1017/S030500410002168X
- de Bruijn, N. G. & Erdős, P. (1951), "A colour problem for infinite graphs and a problem in the theory of relations", Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373, <http://www.math-inst.hu/~p_erdos/1951-01.pdf> (= Indag. Math. 13)
- Byskov, J.M. (2004), "Enumerating maximal independent sets with applications to graph colouring", Operations Research Letters 32 (6): 547–556, DOI 10.1016/j.orl.2004.03.002
- Chaitin, G. J. (1982), "Register allocation & spilling via graph colouring", Proc. 1982 SIGPLAN Symposium on Compiler Construction, pàg. 98–105, ISBN 0-89791-074-5, DOI 10.1145/800230.806984
- Cole, R. & Vishkin, U. (1986), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70 (1): 32–53, DOI 10.1016/S0019-9958(86)80023-7
- Cormen, T. H.; Leiserson, C. E. & Rivest, R. L. (1990), Introduction to Algorithms (1st ed.), The MIT Press
- Dailey, D. P. (1980), "Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete", Discrete Mathematics 30 (3): 289–293, DOI 10.1016/0012-365X(80)90236-8
- Duffy, K.; O'Connell, N. & Sapozhnikov, A. (2008), "Complexity analysis of a decentralised graph colouring algorithm", Information Processing Letters 107 (2): 60–63, doi:10.1016/j.ipl.2008.01.002, <http://www.hamilton.ie/ken_duffy/Downloads/cfl.pdf>
- Fawcett, B. W. (1978), "On infinite full colourings of graphs", Can. J. Math. XXX: 455–457, DOI 10.4153/cjm-1978-039-8
- Fomin, F.V.; Gaspers, S. & Saurabh, S. (2007), "Improved Exact Algorithms for Counting 3- and 4-Colorings", Proc. 13th Annual International Conference, COCOON 2007, vol. 4598, Lecture Notes in Computer Science, Springer, pàg. 65–74, ISBN 978-3-540-73544-1, DOI 10.1007/978-3-540-73545-8_9
- Garey, M. R. & Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5
- Garey, M. R.; Johnson, D. S. & Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pàg. 47–63, doi:10.1145/800119.803884, <http://portal.acm.org/citation.cfm?id=803884>
- Goldberg, L. A. & Jerrum, M. (July 2008), "Inapproximability of the Tutte polynomial", Information and Computation 206 (7): 908–929, DOI 10.1016/j.ic.2008.04.003
- Goldberg, A. V.; Plotkin, S. A. & Shannon, G. E. (1988), "Parallel symmetry-breaking in sparse graphs", SIAM Journal on Discrete Mathematics 1 (4): 434–446, DOI 10.1137/0401044
- Guruswami, V. & Khanna, S. (2000), "On the hardness of 4-coloring a 3-colorable graph", Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pàg. 188–197, ISBN 0-7695-0674-7, DOI 10.1109/CCC.2000.856749
- Halldórsson, M. M. (1993), "A still better performance guarantee for approximate graph coloring", Information Processing Letters 45: 19–23, DOI 10.1016/0020-0190(93)90246-6
- Holyer, I. (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing 10 (4): 718–720, DOI 10.1137/0210055
- Crescenzi, P. & Kann, V. (December 1998), "How to find the best approximation results — a follow-up to Garey and Johnson", ACM SIGACT News 29 (4): 90, DOI 10.1145/306198.306210
- Jaeger, F.; Vertigan, D. L. & Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials", Mathematical Proceedings of the Cambridge Philosophical Society 108: 35–53, DOI 10.1017/S0305004100068936
- Jensen, T. R. & Toft, B. (1995), Graph Coloring Problems, Wiley-Interscience, New York, ISBN 0-471-02865-7
- Khot, S. (2001), "Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring", Proc. 42nd Annual Symposium on Foundations of Computer Science, pàg. 600–609, ISBN 0-7695-1116-3, DOI 10.1109/SFCS.2001.959936
- Kubale, M. (2004), Graph Colorings, American Mathematical Society, ISBN 0-8218-3458-4
- Kuhn, F. (2009), "Weak graph colorings: distributed algorithms and applications", Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures, pàg. 138–144, ISBN 978-1-60558-606-9, DOI 10.1145/1583991.1584032
- Lawler, E.L. (1976), "A note on the complexity of the chromatic number problem", Information Processing Letters 5 (3): 66–67, DOI 10.1016/0020-0190(76)90065-X
- Leith, D.J. & Clifford, P. (2006), "A Self-Managed Distributed Channel Selection Algorithm for WLAN", Proc. RAWNET 2006, Boston, MA, <http://www.hamilton.ie/peterc/downloads/rawnet06.pdf>
- Linial, N. (1992), "Locality in distributed graph algorithms", SIAM Journal on Computing 21 (1): 193–201, DOI 10.1137/0221015
- van Lint, J. H. & Wilson, R. M. (2001), A Course in Combinatorics (2nd ed.), Cambridge University Press, ISBN 0-521-80340-3
- Marx, Dániel (2004), "Graph colouring problems and their applications in scheduling", Periodica Polytechnica, Electrical Engineering, vol. 48, pàg. 11–16, Plantilla:Citeseerx
- Mycielski, J. (1955), "Sur le coloriage des graphes", Colloq. Math. 3: 161–162, <http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf>.
- Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Heidelberg: Springer, p. 42, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.
- Panconesi, Alessandro & Rizzi, Romeo (2001), "Some simple distributed algorithms for sparse networks", Distributed Computing (Berlin, New York: Springer-Verlag) 14 (2): 97–100, ISSN 0178-2770, DOI 10.1007/PL00008932
- Sekine, K.; Imai, H. & Tani, S. (1995), "Computing the Tutte polynomial of a graph of moderate size", Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995), vol. 1004, Lecture Notes in Computer Science, Springer, pàg. 224–233, ISBN 3-540-60573-8, DOI 10.1007/BFb0015427
- Welsh, D. J. A. & Powell, M. B. (1967), "An upper bound for the chromatic number of a graph and its application to timetabling problems", The Computer Journal 10 (1): 85–86, DOI 10.1093/comjnl/10.1.85
- West, D. B. (1996), Introduction to Graph Theory, Prentice-Hall, ISBN 0-13-227828-6
- Wilf, H. S. (1986), Algorithms and Complexity, Prentice–Hall
- Zuckerman, D. (2007), "Linear degree extractors and the inapproximability of Max Clique and Chromatic Number", Theory of Computing 3: 103–128, DOI 10.4086/toc.2007.v003a006
- Zykov, A. A. (1949), "О некоторых свойствах линейных комплексов (On some properties of linear complexes)", Math. Sbornik. 24(66) (2): 163–188, <http://mi.mathnet.ru/eng/msb5974>
- Jensen, Tommy R. & Toft, Bjarne (1995), Graph Coloring Problems, John Wiley & Sons, ISBN 9780471028659
- Normann, Per (2014), Parallel Graph Coloring, DIVA, ISSN 1401-5757, <http://uu.diva-portal.org/smash/record.jsf?pid=diva2:730761>