上海交通大学：数学科学学院专业选修课《图与网络》课程教学大纲

《图与网络》课程教学大纲 课程基本信息(Course Information) 学时 课程代码 (Cre MATH4407 (Course Code dit 48 4学分(Credits)3.0 Hours 课程名称 (中文)图与网络 (Course Name） (英文)Graph theory and networks 课程类型 (Cours Type 专业核心选修 授课对象 (Target 数学科学学院大三、大四学生 Audience) 授课语言 (Language o 中文 Instruction) 开课院系 (School) 数学科学学院 先修课程 后续 线性代数.组合数学 课程 (Prerequisite) nost) 课程 课程负责人 (Cours (Instructor） e (中文300-500字，含课程性质、主要教学内容、课程教学目标等) 由于图语言的普适性，图论中非常重要的多项式，Tute多项式与物理、化学 课程简介（中统计等许多其他学科和领域有密切联系.本课程以Tut多项式为中心，介绍 Tute多项式的基本性质，以及图论中的一些基本结构，如生成树： 一些面 多项式如染色多项式 、流多项式 些经典的组合模型，如图上泊车函数 图上沙堆模型；物理中的Pots模型等的基本概念和性质，及其与Tute多项士 之间的相互关系，相关的经典定理和结果。 (英文300-500字) 课程简介（英 utte polynomial isa polynomial intwo variables which playsan 文) raph theory.It is defined for every undirected graph and contains information (Description) about how the graph is connected.In this course,the concept,properties and

《图与网络》课程教学大纲 课程基本信息（Course Information） 课程代码 （Course Code） MATH4407 *学时 （Cre dit Hours ） 48 *学分（Credits） 3.0 *课程名称 （Course Name） （中文）图与网络 （英文）Graph theory and networks 课程类型 (Course Type) 专业核心选修 授课对象 （Target Audience） 数学科学学院大三、大四学生 授课语言 (Language of Instruction) 全中文 *开课院系 （School） 数学科学学院 先修课程 （Prerequisite） 线性代数, 组合数学 后续 课程 (post） *课程负责人 （Instructor） 马俊 课程 网址 (Cours e Webpa ge) *课程简介（中 文） （Description） （中文 300-500 字，含课程性质、主要教学内容、课程教学目标等） 由于图语言的普适性, 图论中非常重要的多项式, Tutte 多项式与物理、化学、 统计等许多其他学科和领域有密切联系. 本课程以 Tutte 多项式为中心, 介绍 Tutte 多项式的基本性质, 以及图论中的一些基本结构, 如生成树； 一些重要 多项式, 如染色多项式、流多项式； 一些经典的组合模型, 如图上泊车函数和 图上沙堆模型; 物理中的 Potts 模型等的基本概念和性质, 及其与 Tutte 多项式 之间的相互关系, 相关的经典定理和结果. *课程简介（英 文） （Description） （英文 300-500 字） Tutte polynomial is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph and contains information about how the graph is connected. In this course, the concept, properties and

applications of Tutte polynomial will be introduced.Moreover,some basic structures about graphs and classical combinantorial model will be discussed.The elations between these concepts and Tutte polynomial will be studied as well 课程目标与内容(Course objectives and contents) 结合本校办学定位。学生情况、专业人才培养要求，具体描述学习本课程后应该达到的知 识、能力、素质、价值水平. 1.介绍与图有关的一些基本概念(B1,B2,C3,C5) 课程且标 2.讲解图的基本结构：图的生成树的相关性质(B1,B2,C3,C5) Course Objec 介绍拉格朗日反演公式及其应用(B1,B2,C3,C5 介绍图上泊车函数的概念和性质(B1,B2,C3,C5) 5. 介绍图上Tute多项式的概念和性质(B1,B2,C3,C5) 介绍对称群上一些统计量的基本性质(B1,B2,C3,C5) 作业及考 对应课程目 音节教学内容题点) 学 教学形式 课程用改融入点 核要求 领悟抽象和具体 了解与图有关的 的关系，在学习 18 面授 一些基本概念 8 论 领悟抽象和具体 了解图的基木结 的关系，在学习 *教学内容进度第 构：图的生成树 6 面授 2次作业实践中去总结体 B1,B2, 安排及对应课 c3.C5 的相关性质 会世界观和方法 程目标(Cl5 Schedule Requirements 领悟抽象和具体 Course 堂据并会使用拉 的关系，在学习 Objectives) 格朗日反演公式5 面授 1,B2, 音 2次作业：实践中去总结体 及其应用 会世界视和方法c3,5 领悟抽象和具体州 的关系，在学习 第四了解图上泊车函 1.B2 数的概念和性质 面授 次作业实践中去总结街3, 会世界观和方法 掌握图上Tute 领悟抽象和具体 第五 的关系，在学习B1.B2 多项式的概念利2 面授 次作业 性质 实践中去总结体C3,C5 会世界观和方法

applications of Tutte polynomial will be introduced. Moreover, some basic structures about graphs and classical combinantorial model will be discussed. The relations between these concepts and Tutte polynomial will be studied as well. 课程目标与内容（Course objectives and contents） *课程目标 (Course Object) 结合本校办学定位、学生情况、专业人才培养要求，具体描述学习本课程后应该达到的知 识、能力、素质、价值水平。 1．介绍与图有关的一些基本概念(B1,B2,C3,C5) 2．讲解图的基本结构: 图的生成树的相关性质(B1,B2,C3,C5) 3．介绍拉格朗日反演公式及其应用(B1,B2,C3,C5) 4．介绍图上泊车函数的概念和性质(B1,B2,C3,C5) 5. 介绍图上 Tutte 多项式的概念和性质(B1,B2,C3,C5) 6. 介绍对称群上一些统计量的基本性质(B1,B2,C3,C5) *教学内容进度 安排及对应课 程目标 (Class Schedule & Requirements & Course Objectives) 章节 教学内容（要点） 学时 教学形式 作业及考 核要求 课程思政融入点 对应课程目 标 第 一 章 了解与图有关的 一些基本概念 18 面授 6 次作业; 领悟抽象和具体 的关系，在学习 实践中去总结体 会世界观和方法 论 B1,B2, C3,C5 第二 章 了解图的基本结 构: 图的生成树 的相关性质 6 面授 2 次作业; 领悟抽象和具体 的关系，在学习 实践中去总结体 会世界观和方法 论 B1,B2, C3,C5 第 三 章 掌握并会使用拉 格朗日反演公式 及其应用 6 面授 2 次作业; 领悟抽象和具体 的关系，在学习 实践中去总结体 会世界观和方法 论 B1,B2, C3,C5 第 四 章 了解图上泊车函 数的概念和性质 3 面授 1 次作业; 领悟抽象和具体 的关系，在学习 实践中去总结体 会世界观和方法 论 B1,B2, C3,C5 第 五 章 掌 握 图上 Tutte 多项式的概念和 性质 12 面授 4 次作业; 领悟抽象和具体 的关系，在学习 实践中去总结体 会世界观和方法 B1,B2, C3,C5

论 领悟抽象和具体 第六对称群上一些统 的关系，在学习 计量 面授 1次作业 实践中去总结体 1,B2, 章 3,C5 会世界观和方法 论 注1：建议按照教学周周学时编排。 注2：相应章节的课程思政融入点根据实际情况填写。 示例： 考核方式 (1)平时作业30分 (Grading) (2)期末考试70分 教材或参考资 (必含信息：教材名称，作者，出版社，出版年份，版次，书号) 料(Textbooks 1. Bela Bollabos,Modern graph theory,Springer,2002 &Other Richard P.Stanley,SergeyFomin,Bela Boll,Enumerative Combinatorics, Materials) Cambridge UniversityPress,1988 其它(More) 备注(Notes) 备注说明： 1.带*内容为必填项。 2.课程简介字数为300-500字；课程大纲以表述清楚教学安排为宜，字数不限

论 第 六 章 对称群上一些统 计量 3 面授 1 次作业 领悟抽象和具体 的关系，在学习 实践中去总结体 会世界观和方法 论 B1,B2, C3,C5 注 1：建议按照教学周周学时编排。 注 2：相应章节的课程思政融入点根据实际情况填写。 *考核方式 (Grading) 示例： （1）平时作业 30 分 （2）期末考试 70 分 *教材或参考资 料 (Textbooks & Other Materials) （必含信息：教材名称，作者，出版社，出版年份，版次，书号） 1. Bela Bollabos, Modern graph theory, Springer, 2002 2. Richard P. Stanley, SergeyFomin,Bela Boll, Enumerative Combinatorics, Cambridge UniversityPress, 1988 其它（More） 备注（Notes） 备注说明： 1．带*内容为必填项。 2．课程简介字数为 300-500 字；课程大纲以表述清楚教学安排为宜，字数不限