上海交通大学：《离散数学》课程教学资源（讲义）图论——第一章 图的基本概念

第一章：图的基本概念 图的性质 图的同构 图的代数表示 作亚 000000 0000 第一章的主要内容 ●图的基本概念； ●图的代数表示（不讲1.2.4,1.2.5,1.2.6）： 1口回4元4元t至0QC 刘肚利（上海交大CS实监室） 图论第一章：基本概念 1/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ✶➌Ù✛❒❻❙◆ ã✛➘✢❱❣➯ ã✛➇ê▲➠(Øù1.2.4, 1.2.5, 1.2.6)➯ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 1 / 30

第一章：图的基本概念 图的性质 图的同构 图的代数表示 作业 ●00000 0 0000 图的概念 定义1.1.1： 二元组(V(G,E(G)称为图。其中V(G)是非空集合，称 为顶点集，E(G)是V(G)诸顶点之间边的集合。常用G=(VE)表示图。 口回1元，4元↑至0QC 刘肚利（上海交大CS实监室） 图论第一章：基本概念 2/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ã✛❱❣ ➼➶1.1.1➭✥✓✄⑤(V(G), E(G))→➃ã✧Ù➙V(G)➫➎➌✽Ü➜→ ➃➸✿✽➜E(G)➫V(G)➹➸✿❷♠❃✛✽Ü✧⑦❫G = (V, E)▲➠ã✧ ➸✿▲➠➥Ô➯ ❃▲➠➥Ô❷♠✛é❳✧ ⑦➭A, B,C, D➫♦⑤➙è✧❦➉❃(u, v)➇▲uè➅vè✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 2 / 30

第一章：图的基本概念 图的性质 图的同构 图的代数示 作业 ●00000 0000 图的概念 定义1.1.1： 二元组(V(G),E(G)称为图。其中V(G)是非空集合，称 为顶点集，E(G)是V(G)诸顶点之间边的集合。常用G=(VE)表示图。 ●顶点表示事物： ●边表示事物之间的联系。 口回1元，4元↑至0QC 刘肚利（上海变大CS实监室） 图论第一章：基本概念 2/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ã✛❱❣ ➼➶1.1.1➭✥✓✄⑤(V(G), E(G))→➃ã✧Ù➙V(G)➫➎➌✽Ü➜→ ➃➸✿✽➜E(G)➫V(G)➹➸✿❷♠❃✛✽Ü✧⑦❫G = (V, E)▲➠ã✧ ➸✿▲➠➥Ô➯ ❃▲➠➥Ô❷♠✛é❳✧ ⑦➭A, B,C, D➫♦⑤➙è✧❦➉❃(u, v)➇▲uè➅vè✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 2 / 30

第一章：图的本概念 图的性质 图的同构 图的代数表示 作业 ●00000 0000 图的概念 定义1.1.1： 二元利(V(G),E(G)称为图。其中V(G)是非空集合，称 为顶点集，E(G)是V(G)诸顶点之间边的集合。常用G=(VE)表示图。 ●顶点表示事物： ●边表示事物之间的联系。 例：A,B,C,D是四支球队。有向边(w,v)代表u队胜v队。 刘肚利（上海交大CS实监室） 图论第一章：基本概念 2/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ã✛❱❣ ➼➶1.1.1➭✥✓✄⑤(V(G), E(G))→➃ã✧Ù➙V(G)➫➎➌✽Ü➜→ ➃➸✿✽➜E(G)➫V(G)➹➸✿❷♠❃✛✽Ü✧⑦❫G = (V, E)▲➠ã✧ ➸✿▲➠➥Ô➯ ❃▲➠➥Ô❷♠✛é❳✧ ⑦➭A, B,C, D➫♦⑤➙è✧❦➉❃(u, v)➇▲uè➅vè✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 2 / 30

第一章：图的基本概念 图的性质 图的同构 图的代数表示 作业 0●0000 0000 有限图 图G=(VE)中的顶点集合V和边集合E都是有限集合时，称G为有限 图。 +口“4元4元t至0QC 刘肚利（上海交大CS实验室） 图论第一章：基本概念 3/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ❦⑩ã ãG = (V, E)➙✛➸✿✽ÜVÚ❃✽ÜEÑ➫❦⑩✽Ü➒➜→G➃❦⑩ ã✧ ❳❏Ø❭❆Ï❵➨,Ò❅➃➭ V = {v1, v2, · · · , vn}➯➸✿ê➃n✧ E = {e1, e2, · · · , em}➯❃ê➃m✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 3 / 30

第一章：图的基本概念 图的性质 图的同构 图的代数表示 作亚 0●0000 0 0000 有限图 图G=(VE)中的顶点集合V和边集合E都是有限集合时，称G为有限 图。 如果不加特殊说明，就认为： ●V={y1,2,…,yn:顶点数为n。 ●E={e1,e2,·,em:边数为m。 口回1元，4元↑至0QC 刘肚利（上海变大CS实监室） 图论第一章：基本概念 3/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ❦⑩ã ãG = (V, E)➙✛➸✿✽ÜVÚ❃✽ÜEÑ➫❦⑩✽Ü➒➜→G➃❦⑩ ã✧ ❳❏Ø❭❆Ï❵➨,Ò❅➃➭ V = {v1, v2, · · · , vn}➯➸✿ê➃n✧ E = {e1, e2, · · · , em}➯❃ê➃m✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 3 / 30

第一章：图的基木概念 图的性质 图的同构 图的代数表示 作业 00●000 0 0000 有向图、无向图和混合图 ●有方向的边称为有向边，由有向边构成的图称为有向图： 口回1元，4元↑至0QC 刘肚利（上海交大CS实验室） 图论第一章：基本概念 4/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ❦➉ã✦➹➉ãÚ➲Üã ❦➄➉✛❃→➃❦➉❃➜❞❦➉❃✟↕✛ã→➃❦➉ã➯ ❦➉ ❃ek = (vi , vj)➙➜vi➫vj✛❺✚❝➟➜vj➫vi✛❺✚￾❯✧ ◗❦❦➉❃q❦➹➉❃✛ã→➃➲Üã✧ ➄❺➌❻➸✿❷✬é✛❃→➃❣❶✧ ✸Ó➌é➸✿❷♠⑧✸õ❫❃→➃➢❃✧ ➵❦➢❃✛ã→➃õ➢ã✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 4 / 30

第一章：图的基本概念 图的性质 图的同构 图的代数表示 作亚 00●000 0 0000 有向图、无向图和混合图 ●有方向的边称为有向边，由有向边构成的图称为有向图：有向 边ek=(,v)中，是v的直接前趋，v是v的直接后继。 a (b ●既有有向边又有无向边的图称为混合图。 +口“4元4元t至0QC 刘肚利（上海变大CS实监室） 图论第一章：基本概念 4/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ❦➉ã✦➹➉ãÚ➲Üã ❦➄➉✛❃→➃❦➉❃➜❞❦➉❃✟↕✛ã→➃❦➉ã➯❦➉ ❃ek = (vi , vj)➙➜vi➫vj✛❺✚❝➟➜vj➫vi✛❺✚￾❯✧ ◗❦❦➉❃q❦➹➉❃✛ã→➃➲Üã✧ ➄❺➌❻➸✿❷✬é✛❃→➃❣❶✧ ✸Ó➌é➸✿❷♠⑧✸õ❫❃→➃➢❃✧ ➵❦➢❃✛ã→➃õ➢ã✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 4 / 30

第一章：图的基本概念 图的性质 图的同构 图的代数表示 作业 00●000 0 0000 有向图、无向图和混合图 。有方向的边称为有向边，由有向边构成的图称为有向图：有向 边ek=(,v)中，；是v的直接前趋，v是v的直接后继。 a b ●既有有向边又有无向边的图称为混合图。 。只与一个顶点相关联的边称为自环。 刘肚利（上海交大CS实验室） 图论第一章：基本概念 4/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ❦➉ã✦➹➉ãÚ➲Üã ❦➄➉✛❃→➃❦➉❃➜❞❦➉❃✟↕✛ã→➃❦➉ã➯❦➉ ❃ek = (vi , vj)➙➜vi➫vj✛❺✚❝➟➜vj➫vi✛❺✚￾❯✧ ◗❦❦➉❃q❦➹➉❃✛ã→➃➲Üã✧ ➄❺➌❻➸✿❷✬é✛❃→➃❣❶✧ ✸Ó➌é➸✿❷♠⑧✸õ❫❃→➃➢❃✧ ➵❦➢❃✛ã→➃õ➢ã✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 4 / 30

第一章：图的基本概念 图的性质 图的同构 图的代数表示 作业 00●000 0 0000 有向图、无向图和混合图 。有方向的边称为有向边，由有向边构成的图称为有向图：有向 边ek=(y,y)中，y:是v的直接前趋，v是y的直接后继。 a b ●既有有向边又有无向边的图称为混合图。 ·只与一个顶点相关联的边称为自环。 ·在同一对顶点之间存在多条边称为重边。 含有重边的图称为多重图。 刘肚利（上海交大-CS实验室） 图论第一章：基本概念 4/30

✶➌Ù➭ã✛➘✢❱❣ ã✛✺➓ ã✛Ó✟ ã✛➇ê▲➠ ❾➆ ❦➉ã✦➹➉ãÚ➲Üã ❦➄➉✛❃→➃❦➉❃➜❞❦➉❃✟↕✛ã→➃❦➉ã➯❦➉ ❃ek = (vi , vj)➙➜vi➫vj✛❺✚❝➟➜vj➫vi✛❺✚￾❯✧ ◗❦❦➉❃q❦➹➉❃✛ã→➃➲Üã✧ ➄❺➌❻➸✿❷✬é✛❃→➃❣❶✧ ✸Ó➌é➸✿❷♠⑧✸õ❫❃→➃➢❃✧ ➵❦➢❃✛ã→➃õ➢ã✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶➌Ù➭➘✢❱❣ 4 / 30