GRAPH THEORY
本學期的第四次「啟研講壇」系列活動將圍繞「圖論」這一學科展開。圖論是一門古老的學科，是數學中擁有廣泛應用的一個分支。用點表示對象，用兩點間的連線表示對象間的某種特定關係，圖能把紛雜的信息變得有序、直觀、清晰，而圖論正是以圖為研究對象的學科。
作為引入，讓我們先看看以下三個情境和問題。
01
主 題 引 入
01
在我們日常生活中，色彩的運用涉及很多領域。在常用的地圖中，為了方便識別，所有的行政區域都被染上了顏色用於識別，相鄰的兩個行政區域所染的顏色不同。那你有想過，需要多少種顏色才能完成一張地圖的染色嗎？
02
在18世紀的哥尼斯堡城中，一條橫穿全城的河流把城市分成四塊，於是人們建造了7座各具特色的橋，把哥尼斯堡城連城一體。這些形態各異的小巧吸引了眾多的旅客，同時一個有趣問題在居民中傳開：能否從A，B，C，D四個陸地中的任一個地方出發一次走遍所有的7座橋，而且每座橋都無重複的只通過一次？
03
在上海交通大學閔行校區的平面地圖中，如何能立刻找到從主圖到包圖最快的一條路嗎？假如我們想知道圖中任意兩點之間的最短路徑呢？
圖論在自然科學、運籌學、計算機科學、信息論、控制論、通信科學、社會科學等各個領域都有着廣泛的應用。
隨着生產管理、軍事、交通運輸的實際需要，以及計算機技術的進步，圖論的理論研究以及實際應用正飛速發展。
本次講座中將着重介紹與圖論相關的幾類問題，包含以下三個模塊：
· 圖論中的邊權類問題：最短路徑問題，廣度優先和深度優先搜索，最小生成樹
· 圖論中的構造性問題：拉姆齊定理，Prufer序列，四色問題
· 圖論與NPC問題：對難解問題和求解複雜度的思考
02
講 座 信 息
主講人：方俊傑
中國大學生程序設計競賽區域賽金牌
國際大學生程序設計競賽中國賽區銀牌
全國青少年信息學聯賽國家一等獎
時間：12月18日（三）17:10-20:40
地點：學院樓323
參加講座將提供素拓獎勵
歡迎同學們積極前來:)
「
掃描左側二維碼
關注巴院科創
了解更多巴院科創資訊
文案：周清實
排版：游暢
留言列表