在无向图中， 没有两个顶点是邻接的顶点集称为独立集。当任何顶点加到这个集合中，它不再是一个独立集，则称该独立集为最大独立集。在棋盘上放8个皇后，使得没有一个能捕捉另一个，试用图论术语叙述这个问题。
举一反三
- 在无向图中， 没有两个顶点是邻接的顶点集称为独立集。当任何顶点加到这个集合中，它不再是一个独立集，则称该独立集为最大独立集。在下图中，找出两个不同大小的最大独立集。[img=451x366]1777142413238e8.png[/img]
- 在无向图中有一个顶点集合，如果不在该集合中的每个顶点至少与该集合中的一个顶点邻接，则称该集合是支配集。如果一个支配集的任何真子集都不是支配集，则称该支配集为最小支配集。设棋盘的64个方块用64个顶点表示，如果两顶点对应的两个方块是在同一行，同一列或同一对角线上，则这两顶点之间有一条边。已知5个皇后能被放在棋盘上，使它们支配所有64个方块，而且5是必须的最小皇后数。再用图论名词叙述这一结论 。
- 简单图中顶点的支配集是顶点的一个集合，使得其他每个顶点都与这个集合中至少一个顶点是相邻的。带最少顶点数的支配集称为最小支配集。求下列所给的图的最小支配集。[img=235x188]179ca493d8483d6.png[/img]
- 若图的一组顶点集合中的任何两个顶点都不相邻，则这个顶点集合称为独立的。图的独立数是该图的独立顶点集中的最大顶点个数。下列图的独立数是什么?[tex=1.286x1.214]O8Qg2Jw2e1h10vsY7JlITw==[/tex]
- 若图的一组顶点集合中的任何两个顶点都不相邻，则这个顶点集合称为独立的。图的独立数是该图的独立顶点集中的最大顶点个数。下列图的独立数是什么?[tex=1.214x1.214]09ZXoxVTCdKWQQldwFb9rQ==[/tex]