请输入您要查询的字词:

 

单词 KpartiteGraph
释义

k-partite graph


A k-partite graph is a graph with a chromatic numberMathworldPlanetmath of k.

An alternate definition of a k-partite graph is a graph where the vertices are partitioned into k subsets with the following conditions:

  1. 1.

    No two vertices in the same subset are adjacent.

  2. 2.

    There is no partitionMathworldPlanetmathPlanetmath of the vertices with fewer than k subsets where condition 1 holds.

These two definitions are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. Informally, we see that a colour can be assigned to all the vertices in each subset, since they are not adjacent to one another. Furthermore, this is also an optimal colouring, since the second condition holds.

An example of a 4-partite graph:

随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 1:26:13