Course title
F00220002
Network Theory

 MORINO Hiroaki
Middle-level Diploma Policy (mDP)
Program / Major mDP Goals Courses
Fundamental Mechanical Engineering F 産業界や社会の要請を把握して解決するべき課題を設定し、さまざまな工学分野の知識を関連付けながら設計生産技術を活用することで、立案した構想に従って研究を進め課題を解決することができる。 Sub
Advanced Mechanical Engineering F 産業界や社会の要請を把握して解決するべき課題を設定し、機械工学の学理を応用して異分野を含む融合分野で革新的な機能を創成することができる。 Sub
Environment and Materials Engineering B 地球環境や地域社会との調和を見据えて、さまざまな工学分野に関わる問題を解決することができる。 Sub
Chemistry and Biotechnology B 地球環境や地域社会との調和を見据えて、さまざまな工学分野に関わる問題を解決することができる。 Sub
Electrical Engineering and Robotics D 電気工学や関連する工学の技術分野を課題に適用し、社会の要求を解決するために応用することができる。 Sub
Advanced Electronic Engineering E 専門的デザイン課題について解決する能力を身に付けることができる。 Sub
Information and Communications Engineering B-3 最先端のシステムやネットワークに対応できる高度な専門知識や技能を習得することができる。 Main
Urban Infrastructure and Environment G ⼟⽊⼯学における現実の問題について、⼯学・専⾨基礎知識を⽤いて理解・解決することができる。 Sub
Purpose of class
Students understand how to solve optimization problem in graph theory, and understand the concept of complex networks, how to analyze them and apply to actual problems. They understand formulations of linear programming and solve them.
Course description
This course provides basic knowledge of graph theory and linear programming. Graph theory is a powerful tool to analyze the fundamental characteristics of a variety of systems referred to as ”networks” such as information and communication networks, social networks and so on. Linear programming is a common tool to solve a variety of optimization problems such as network flow problems.
It will be useful to learn linear programming before taking the course of ”pattern recognition” held in the second semester.
In the latter half of this course, students experience practice of computer programming on graph theory problems and linear programming using Python．
Goals and objectives
  1. Students can understand the principle of modelling communication networks with graphs and being able to solve some optimization problems using graphs.
  2. Students can understand problem formulation and solving of linear programming.
  3. Students can understand description of graph theory problems and linear programming problem and solution of the problems using Python language.
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 Mid-term examination End-term examination Mini-exams Total.
1. 25% 0% 0% 25%
2. 25% 0% 0% 25%
3. 0% 35% 15% 50%
Total. 50% 35% 15% -
Evaluation method and criteria
Mid-term examination(50%) , end-term examination(35%) and Mini exams(15%). You can earn the credit when the total score is 60 or higher out of 100. You will get the score of 60 when you will able to solve approximately 70% of problem practices delivered in each class.
Language
Japanese
Class schedule

 Class schedule HW assignments (Including preparation and review of the class.) Amount of Time Required
1. Graph theory （Part I)

　- Introduction
　- Konigsberg bridge problem
　- Definitions of notations
　 - Walk, path, loop，closed path, cycle
　- Eulerian path and semi-Eulerian graph
- Eulerian cycle and Eulerian graph
- Graphs where cost is given to each edge
- Shortest path tree problem
- Dijkstra algorithm 		Reading the handout delivered in advance entitled ”Graph theory (Part I)” 190minutes
2. Graph theory （Part II)

- Notion of connectivity for analyzing reliability

- Metrics of connectivity
　-　Vertex (Node) connectivity　　
-　Edge (Link) connectivity
- Disjoint path, Menger’s theorem
- Flow network
- Maximum flow problem 		Reading the handout delivered in advance entitled ”Graph theory (Part II)” 190minutes
3. Graph theory （Part III)
- Cut and minimum cut in directed graphs　
- Max-flow min-cut theorem 		Reading the handout delivered in advance entitled ”Graph theory (Part III)” 270minutes
4. Advanced graph theory
　- Complex networks
- Analyzing social networks using complex networks 		Reading the handout delivered in advance entitled ”Advanced graph theory” 270minutes
5. Linear Programming (Part I)
- Overview
- Model formulation example:
for a maximum network flow problem
- Graphical solution
- Simplex method 		Reading the handout delivered in advance entitled ”Linear Programming (Part I)” 190minutes
6. Problem practice to review classes from 1st to 5th. Reviewing handouts from the 1st to the 5th. 190minutes
7. Mid-term examination and a lecture on the answers Reviewing handouts from the 1st to the 7th. 270minutes
8. Linear Programming (Part II)
- Minimization problem, Dual Problem,Sensitivity analysis 		Reading the handout delivered in advance entitled ”Linear Programming (Part II)” 190minutes
9. Programming exercise(Part I)
- Basic of Python language
- Basic of programming using NetworkX library 		Reading the handout delivered in advance entitled ”Programming exercise (Part I)” 190minutes
10. Programming exercise(Part II)
- Programming to solve network flow problems 		Reading the handout delivered in advance entitled ”Programming exercise (Part II)” 190minutes
11. Programming exercise(Part III)
- Programming to solve linear programming problems 		Reading the handout delivered in advance entitled ”Programming exercise (Part III)” 190minutes
12. Programming exercise(Part IV)
- Programming to solve transportation problems 		Reading the handout delivered in advance entitled ”Programming exercise (Part IV)” 270minutes
13. Problem practice to review classes from 8th to 12th Reviewing classes from the 8th to the 12th. 190minutes
14. End-term examination and a lecture on the answers Reviewing classes from the 8th to the 13th. 190minutes
Total. - - 2980minutes
Feedback on exams, assignments, etc.
ways of feedback specific contents about "Other"
Feedback in/outside the class.
Textbooks and reference materials
None
Prerequisites
Recommended to take the course of ”Information and Communication Network”.
Office hours and How to contact professors for questions
  • Lunch time on the day of each class
Regionally-oriented
Non-regionally-oriented course
Development of social and professional independence
  • Course that cultivates a basic problem-solving skills
Active-learning course
About half of the classes are interactive
Course by professor with work experience
Work experience Work experience and relevance to the course content if applicable
N/A N/A
Education related SDGs:the Sustainable Development Goals
  • 9.INDUSTRY, INNOVATION AND INFRASTRUCTURE
Last modified : Sat Mar 14 13:43:28 JST 2026