《图论初步课件图论初步》由会员分享，可在线阅读，更多相关《图论初步课件图论初步（52页珍藏版）》请在金锄头文库上搜索。
1、图论初步,一、关于图论,七桥问题的图,例1 证明任何6个人中，其中总存在3个人，他们或者相互认识或者相互不认识.,例2 9名数学家在一次国际数学会议上相遇，已知他们任意3个人中至少有两个可以用一种语言对话，且每个数学家至多会说3种语言，证明至少存在在3名数学家可以用同一种语言对话.,例3 有4对夫妇参加一次舞会，会间某些人两两做舞伴跳舞（夫妇之间没跳过舞）.会后，其中一位赵先生统计其余每位与会者跳舞的次数，发现他们跳舞的次数各不相同，问： （1）赵夫人跳了几次舞？ （2）赵先生跳了几次舞？ （3）谁与谁是夫妻？,课后练： IMO评议会有34个国家参加，每个国家有领队和副领队两个人参加，会前某些
2、与会者之间握手相互问候（领队与他的副手不握手）.会后，主办国领队统计其余每位与会者握手的次数，发现他们握手的次数各不相同，问：主办国副领队与多少个人握过手.(IMO26),二、图论基本知识,观察如下一些现象： （1）一群人中，有些人相互认识，有些人相互不认识； （2）若干只球队比赛，有些队之间相互比赛过，有些队之间没有比赛过； （3）若干城市中，有些城市相互之间有直通航线，另一些城市相互之间无直通航线. ,这些现象有以下特点： （1）存在一些“对象”：如人群，城市，球队等； （2）对象之间存在某种二元“关系”：如相互认识，相互比赛过，有直通航线，相互握过手等.,用点来表示上述现象的“对象”，用连接两点之间的“线”来表示上述现象中的“关系”,图,n 阶 图,同构,同构,同构,这是因为,七桥问题的图,必是连通图,所以此图不是哈密顿图,所以此图不是哈密顿图，无法实现题中想法.,七桥问题的图,三、例题,三、例题,
