求一个离散数学 图论模型

图论是应用数学的一个重要的分支.它是研究客观对象之间二元关系的一门学科，一个图是由点和线构成的，点代表的是客观对象,边代表是两个对象之间的某种联系.一个图为某种二元关系提供了一个数学模型.在现实生活中,凡是能转化为有关二元关系的问题都可以建立该的问题图论模型,化为图论问题解决,而现实生活中,二元关系无处不在,因此图论模型随处可见,因此图论的应用范围愈来愈广泛,克希霍夫 (Kirchhoff) 利用图论解决了电网中的电流问题,凯莱(Cayler)利用图论的概念解决了有机化学中同分异构体的计数问题,现在图论在各种物理学科,工程领域,社会学科都有应用,在计算机科学中一些领域,如计算机语言, 计算机算法,数据库,操作系统,人工智能,网络理论,数值计算都能找到它的应用.由于图论应用的广泛性,我只好给你提供一些重要的图论模型:
1.七桥问题,河水隔开的陆地看成点,连结两块陆地的桥看成线,化为图,这是图论中的行遍性问题.
2.平面地图着色问题,国家看成点,两相邻国家对应的点之间存在一条线,化为图,这是图论中的结点着色问题.
3.最短路径问题,最小生成树问题,应用十分广泛
4.同分异构体的计数问题,C原子表示点,两C原子由化学键相连,表示一条边,化为图,这是组态计数问题.
5.排课问题.人,课代表点,某人能代某课,对应点之间有一条边,化为图,这是两部图匹配问题
6.城市街道监视器的配制,拉圾站的配制无不是图论问题.化为图论的覆盖,独立集问题.
太多太多了,为了轻松一些,我提供两个有趣的题,要解决它需要化为图模型,
1.世界上任意6个人,必有3个人互相认识,或3个人互相不认识.
2.在一个集会上,每个男士均认识5位女士,每个女士均认识5位男士,则男士女士人数一样多,每个女士均可与它认识的男士跳舞.