Course title
F08457003
Network theory

 morino hiroaki Click to show questionnaire result at 2018
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 learn computer programming of graph theory problems and linear programming using Python．
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.
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.
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
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 Mid-term examination End-term examination Assignments Total.
1. 25% 0% 0% 25%
2. 20% 0% 0% 20%
3. 0% 35% 20% 55%
Total. 45% 35% 20% -
Evaluation method and criteria
Mid-term examination(45%) , end-term examination(35%) and Assignments(20%). You will take the credit when the total score is equal to or larger than 60.out of 100. You will get the score of 60 when you will able to approximately 70% of problem practices delivered in each class.
Textbooks and reference materials
None
Prerequisites
Recommended to take the course of "Information and Communication Networks I" in the 2nd grade.
Office hours and How to contact professors for questions
  • Lunch time on the day of each class
Relation to the environment
Non-environment-related course
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 applicatable
N/A N/A
Last modified : Thu May 30 04:24:37 JST 2019