KA102001 Discrete Mathematics II

Hiroshima University Syllabus

Japanese

Academic Year 2024Year School/Graduate School School of Informatics and Data Science

Lecture Code KA102001 Subject Classification Specialized Education

Subject Name 離散数学II

Subject Name
（Katakana）リサンスウガク２

Subject Name in
English Discrete Mathematics II

Instructor FUJITA SATOSHI

Instructor
(Katakana) フジタ　サトシ

Campus Higashi-Hiroshima Semester/Term 1st-Year,  Second Semester,  3Term

Days, Periods, and Classrooms (3T) Weds1-4：ENG 107

Lesson Style Lecture Lesson Style
(More Details) 　

Lecture

Credits 2.0 Class Hours/Week 　 Language of Instruction B : Japanese／English

Course Level 2 : Undergraduate Low-Intermediate

Course Area（Area） 25 : Science and Technology

Course Area（Discipline） 02 : Information Science

Eligible Students

Keywords Graph theory, Euler graph, degree sequence, planar graph, connectivity of graph, matching, coloring

Special Subject for Teacher Education 　 Special Subject 　

Class Status
within Educational
Program
(Applicable only to targeted subjects for undergraduate students)
Criterion referenced
Evaluation
(Applicable only to targeted subjects for undergraduate students) Integrated Arts and Sciences
（Knowledge and Understanding）
・Knowledge and understanding of the importance and characteristics of each discipline and basic theoretical framework.
（Abilities and Skills）
・The ability and skills to specify necessary theories and methods for consideration of issues.

Computer Science Program
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.

Data Science Program
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.

Intelligence Science Program
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.

Class Objectives
/Class Outline The goal of this class is understand the basic concept and key properties in the graph theory.

Class Schedule 1. Introduction. Guidance, Preliminaries
2. Subgraph, operations on graphs, degree sequence
3. Path, circuits, Eulerian graphs
4.  Connected graph, blocks
5. Eigenvalues of graphs
6. Matrix-tree theorem
7.  Planar graphs, Euler's formula
8. Crossing number, planarity test
9.  Matching, cover, factorization
10. Minimum cut and maximum flow
11. Graphs and groups, Cayley graphs
12. Graph isomorphism
13.  Vertex coloring, chromatic numb er
14. Edge coloring
15. Perfect graphs

Quiz of about 15 min for every class; five reports; and final exam.

Text/Reference
Books,etc. Not used (pdf file will be distributed)

PC or AV used in
Class,etc. 　

(More Details) Lecture (video projector)

Learning techniques to be incorporated 　

Suggestions on
Preparation and
Review It should be difficult to understand the logics used in the proof of key theorems, but it is strongly recommended to follow it through prep review and exercises.

Requirements

Grading Method Exercise + report (50%)
Final exam (50%)

Practical Experience

Summary of Practical Experience and Class Contents based on it

Message

Other

Please fill in the class improvement questionnaire which is carried out on all classes.
Instructors will reflect on your feedback and utilize the information for improving their teaching.

Academic Year	2024Year	School/Graduate School	School of Informatics and Data Science
Lecture Code	KA102001	Subject Classification	Specialized Education
Subject Name	離散数学II
Subject Name （Katakana）	リサンスウガク２
Subject Name in English	Discrete Mathematics II
Instructor	FUJITA SATOSHI
Instructor (Katakana)	フジタ　サトシ
Campus	Higashi-Hiroshima	Semester/Term	1st-Year, Second Semester, 3Term
Days, Periods, and Classrooms	(3T) Weds1-4：ENG 107
Lesson Style	Lecture	Lesson Style (More Details)
Lecture
Credits	2.0	Class Hours/Week		Language of Instruction	B : Japanese／English
Course Level	2 : Undergraduate Low-Intermediate
Course Area（Area）	25 : Science and Technology
Course Area（Discipline）	02 : Information Science
Eligible Students
Keywords	Graph theory, Euler graph, degree sequence, planar graph, connectivity of graph, matching, coloring
Special Subject for Teacher Education		Special Subject
Class Status within Educational Program (Applicable only to targeted subjects for undergraduate students)
Criterion referenced Evaluation (Applicable only to targeted subjects for undergraduate students)	Integrated Arts and Sciences （Knowledge and Understanding）・Knowledge and understanding of the importance and characteristics of each discipline and basic theoretical framework. （Abilities and Skills）・The ability and skills to specify necessary theories and methods for consideration of issues. Computer Science Program （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis. Data Science Program （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis. Intelligence Science Program （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.
Class Objectives /Class Outline	The goal of this class is understand the basic concept and key properties in the graph theory.
Class Schedule	1. Introduction. Guidance, Preliminaries 2. Subgraph, operations on graphs, degree sequence 3. Path, circuits, Eulerian graphs 4. Connected graph, blocks 5. Eigenvalues of graphs 6. Matrix-tree theorem 7. Planar graphs, Euler's formula 8. Crossing number, planarity test 9. Matching, cover, factorization 10. Minimum cut and maximum flow 11. Graphs and groups, Cayley graphs 12. Graph isomorphism 13. Vertex coloring, chromatic numb er 14. Edge coloring 15. Perfect graphs Quiz of about 15 min for every class; five reports; and final exam.
Text/Reference Books,etc.	Not used (pdf file will be distributed)
PC or AV used in Class,etc.
(More Details)	Lecture (video projector)
Learning techniques to be incorporated
Suggestions on Preparation and Review	It should be difficult to understand the logics used in the proof of key theorems, but it is strongly recommended to follow it through prep review and exercises.
Requirements
Grading Method	Exercise + report (50%) Final exam (50%)
Practical Experience
Summary of Practical Experience and Class Contents based on it
Message
Other
Please fill in the class improvement questionnaire which is carried out on all classes. Instructors will reflect on your feedback and utilize the information for improving their teaching.

Back to syllabus main page