GHO
图论入门
前言
可能有锅
内容
比较基础的定义
图的定义 : 一个G={V,E,w}G=\{V,E,w\}G={V,E,w} 分别为边集,点集,关系
也有二元组定义
重边的定义:(u,v)(u,v)(u,v)重复的边
独立集(或者稳定集)定义:图 $G $中两两互不相邻的顶点构成的集合
二部图(或二分图)定义:设G=(V,E)G=(V,E)G=(V,E)是一个无向图,如果顶点VVV可分割为两个互不相交的子集(A,B)(A,B)(A,B),并且图中的每条边(i,j)(i,j)(i,j)所关联的两个顶点iii和jjj分别属于这两个不同的顶点集
图的色数χ(G)\chi(G)χ(G) 给定图形边缘所需的最少颜色数量称为图形的边色数。
一个图是k−k-k−分的当且仅当色数为kkk
子图的定义 V(H)⊆V(G),E(H)⊆E(G)V(H) \subseteq V(G),E(H)\subseteq E(G)V(H)⊆V(G),E(H)⊆E(G)或者说GGG包含HHH
同构是在数学对象之间定义的一类映射,它能揭示出在这些对象的属性或者操作之间存在的关系。若这两个 ...