请输入您要查询的字词:

 

单词 ChromaticNumber
释义

chromatic number


The chromatic numberMathworldPlanetmath of a graph is the minimum number of colours required to colour it.

Consider the following graph:

\\xymatrixA\\ar@-[r]&B\\ar@-[r]\\ar@-[d]&C\\ar@-[r]\\ar@-[dl]&F\\ar@-[dl]&D\\ar@-[r]&E&

This graph has been coloured using 3 colours. Furthermore, it’s clear that it cannot be coloured with fewer than 3 colours, as well: it contains a subgraphMathworldPlanetmath (BCD) that is isomorphic to the complete graphMathworldPlanetmath of 3 vertices. As a result, the chromatic number of this graph is indeed 3.

This example was easy to solve by inspection. In general, however, finding the chromatic number of a large graph (and, similarly, an optimal colouring) is a very difficult (NP-hard) problem.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 10:42:57