圖論1.1圖的基本概念

2021-02-19 小興且愛學

圖的基本概念

圖論起源於一個非常經典的問題——柯尼斯堡（Konigsberg）七橋問題。1738年，瑞士數學家歐拉( Leornhard Euler)解決了柯尼斯堡問題。由此圖論誕生。歐拉也成為圖論的創始人。


先來看二元關係的概念：

如果一個集合滿足以下條件之一：

（1）集合非空，且它的元素都是有序對；

（2）集合是空集，

則稱該集合為一個二元關係.

設V是非空集，V上的二元關係e是V上的元素對，即e∈V×V. 集V和定義在V上的二元關係集E的有序二元組（V,E）被稱為數學結構.

圖的概念：



所謂圖，是指數學結構（V,Eφ），其中V是非空集，Eφ是定義在V上的二元關係集（可以是重集），它由函數φ：E→V×V確定.

若Eφ中的元素全為有序對（x,y）則稱其為有向圖D，從x到y的有向邊，x是起點，y是終點，起點終點統稱端點.

若Eφ中的元素全為無序對{x,y}，則稱其為無向圖G.連接x和y的邊.

--

V為該圖的頂點集，Eφ為該圖的邊集，V中的元素被稱為頂點，Eφ中的元素被稱為邊，φ被稱為點與邊的關聯函數.

邊與它的兩端點被稱為關聯的，與同一條邊關聯的兩端點或者同一個端點關聯的兩邊被稱為相鄰的.

兩端點相同的邊被稱為環，有公共起點和終點的兩條邊被稱為重邊或平行邊，兩端點相同但方向相反的兩條有向邊被稱為對稱邊.




一些特殊的圖：

頂點或者邊都有標號的圖形稱為標號圖.

含重邊的圖稱為重圖.

無環且無重邊的圖稱為簡單圖.

對於無向圖G，將G中的每一條邊e用兩條與e有相同端點的對稱邊替代後得到的有向圖稱為G的對稱有向圖.無向圖可以視為特殊的有向圖.

去掉有向圖邊上的方向得到的無向圖稱為基圖.

將無向圖每條邊都指定方向而得到的有向圖稱為定向圖.

圖的頂點數被稱為階，階為1的簡單圖稱為平凡圖，邊數為0的圖被稱為無邊圖，也稱為空圖，頂點數和邊數都是有限的圖稱為有限圖.

相關焦點

  • 圖論與圖學習(一):圖的基本概念
    近日，數據科學家 Mal Fabien 在其博客上發布了涉及圖論、圖算法和圖學習的系列文章《圖論與圖學習》。本文是其中第一篇，介紹了圖的一些基礎知識並給出了 Python 示例。更多文章和對應代碼可訪問：https://github.com/maelfabien/Machine_Learning_Tutorials。本文涵蓋以下主題：圖是什麼？如何存儲圖？
  • 2007年度國家精品課程:集合論與圖論
    哈工大報訊  離散教學是計算機科學的重要工具，也是軟體及其應用必不可少的數學工具，內容包括集合論、圖論、近世代數和數理邏輯。我校《集合論與圖論》涵蓋了前兩部分。集合論是整個數學的基礎；圖論可以看成是集合論的一個應用。
  • 圖論Graph theory
    有關圖論的基本定義，請參閱圖論術語表。Refer to the glossary of graph theory for basic definitions in graph theory.一個圖的圖畫 A drawing of a graph01—定義 Definitions圖論中的定義各不相同。
  • 5月,《圖論》(原書第五版)中譯本來啦
    ▋關於第五版延續了第一版和第三版的基本思路：「當前, 讀者為了準備好迎接將來可能出現的新生事物，哪些領域、方法和結果才應該是組成初等圖論課程的中心內容？」這個概念最先由Robertson 和Seymour 引進, 作為證明圖子式定理的技術工具, 但後來它超越了原來的功能, 成為更基礎的工具：他們定義了一個範例來確定圖中的高連通部分. 在早期的研究中, 與定義某種子結構(例如高連通子圖、子式或拓撲子式) 不一樣, 糾纏並不試圖利用諸如頂點、邊, 或連通路來確定這種子結構, 而是通過把低維的分離集定向來間接地確定想要的子結構.
  • 一文帶你入門圖論和網絡分析(附Python代碼)
    本文從圖的概念以及歷史講起，並介紹了一些必備的術語，隨後引入了networkx庫，並以一個航班信息數據集為例，帶領讀者完成了一些基本分析。簡介俗話說一圖勝千言。但是「圖」（Graph）說的遠不止於此。以圖形式呈現的數據可視化能幫助我們獲得見解，並基於它們做出更好的數據驅動型決策。
  • 應遊戲而生的數學圖論，多棲發展的數學家哈密頓，傳奇人生
    歐拉要求在一個圖中尋找滿足&34;的路線，這樣的路線後來在圖論中被稱為歐拉迴路。而具有歐拉迴路的圖稱為歐拉圖。與之表面相似，實際完全不同的哈密頓問題則要求在一個圖中尋找滿足&34;的路線，這樣的路線後來在圖論中被稱為哈密頓圈，而具有哈密頓圈的圖稱為哈密頓圖或說圖是哈密頓的。歐拉問題與哈密頓問題已經成為現在圖論的重要組成部分。
  • 應遊戲而生的數學圖論,多棲發展的數學家哈密頓,傳奇人生
    但在數學史上，哈密頓週遊世界的遊戲和歐拉的七橋問題是兩例標誌性建築，播下了圖論誕生與發展的種子。如下圖給出了這遊戲的一種正確玩法。讓我們對照一下歐拉與哈密頓研究的問題。歐拉要求在一個圖中尋找滿足「從一個頂點出發，沿邊行進，無遺漏走遍所有的邊，每一邊只許經過一次回到出發點」的路線，這樣的路線後來在圖論中被稱為歐拉迴路。而具有歐拉迴路的圖稱為歐拉圖。
  • 圖論的各種基本算法
    原標題：圖論的各種基本算法 本篇主要涉及到圖論的基本算法，不包含有關最大流的內容。圖論的大部分算法都是由性質或推論得出來的，想樸素想出來確實不容易。 先判斷圖是否是連通圖。返回0代表沒有歐拉迴路或者歐拉路徑，返回1代表有歐拉路徑，返回2代表有歐拉迴路。
  • 2017西安圖論與組合數學論壇在我校舉辦
    西工大新聞網10月27日電（白延東）10月20日至22日，2017西安圖論與組合數學論壇在我校成功舉辦。本次論壇由西北工業大學主辦，理學院、研究生院學科建設辦公室承辦，應用數學系圖論與組合數學研究團隊組織執行。
  • 圖論的起源發展及其應用
    本課程中，介紹了圖論中的基本概念和網絡科學使用的工具，可以幫助認識真實網絡的關鍵性質。隨後的章節將系統地研究這些網絡性質，深入理解這些網絡性質在認識複雜系統方面發揮的重要作用。　　課程PPT截選
  • 2016年國際圖論研討會在青海師範大學成功召開
    10月29日至11月2日青海省絲綢之路經濟帶研究院系列活動——2016年國際圖論研討會於在青海師範大學舉行。青海師範大學副校長趙海興代表學校在開幕式上致歡迎辭。　　本次研討會邀請了包括享譽國際圖論專家、匈牙利科學院院士Miklós Simonovits在內的來自美國、英國、澳大利亞、匈牙利、臺灣的圖論研究專家。會議安排了14場學術報告。
  • 搭建圖與網絡之間的橋梁：網絡科學的下一個突破在哪裡？
    在大數據革命的推動下，網絡這一概念已經成為描述對物理、生物和社會現象的無數經驗觀察的強大工具。 與網絡類似，圖是由若干頂點和連接這些頂點的邊構成的圖形，研究圖的數學分支也就是圖論。受社會學和經濟學中開創性研究的啟發，網絡科學從圖論中繼承了其最初的概念。然而自此之後，圖論和網絡科學就分道揚鑣了，無論是它們研究的問題，還是研究它們的學術團體都幾乎沒有重疊。
  • 圖論是一個非常受歡迎的離散數學領域,應用於無數實際問題
    圖論是一個非常受歡迎的離散數學領域，不僅有許多理論發展，而且還有無數應用於實際問題。作為一個研究領域，圖論仍然相對年輕，但它正在迅速成熟，在過去的幾十年中已經發現了許多深刻的結果。圖的理論可以粗略地劃分為兩個分支：無向圖和有向圖（有向圖）的區域。
  • plc梯形圖編程實例_plc梯形圖編程基本概念
    plc梯形圖編程中，用到以下四個基本概念： 01軟繼電器 PLC梯形圖中的某些編程元件沿用了繼電器這一名稱，如輸入繼電器、輸出繼電器、內部輔助繼電器等，但是它們不是真實的物理繼電器，而是一些存儲單元（軟繼電器），每一軟繼電器與PLC存儲器中映像寄存器的一個存儲單元相對應
  • 梁的布置與基本概念
    橋梁在生活中很常見，可是梁的布置與基本概念是什麼樣的呢？1梁的布置設在曲線上的鋼筋混凝土簡支梁式橋，每孔梁仍是直的，於是各孔梁中線的連接線成為折線，以適應梁上曲線線路之需要。但若按圖1所示布置，使線路中線與梁的中線在梁端相交，則由圖可以看出，線路中線總是偏在梁跨中線的外側，當列車過橋時，外側那片梁必然受力較大；況且列車運行時要產生離心力，使外側的一片梁受力較大的現象更加嚴重。為了使兩片梁受力較為均衡，合理的布置方案應把梁的中線向曲線外側適當移動。
  • 純數學|圖論 集聚係數 Clustering Coefficient
    在圖論中，集聚係數（也稱群聚係數、集群係數）是用來描述一個圖中的頂點之間結集成團的程度的係數。具體來說，是一個點的鄰接點之間相互連接的程度。例如生活社交網絡中，你的朋友之間相互認識的程度。有證據表明，在各類反映真實世界的網絡結構，特別是社交網絡結構中，各個結點之間傾向於形成密度相對較高的網群。也就是說，相對於在兩個節點之間隨機連接而得到的網絡，真實世界網絡的集聚係數更高。
  • 科學家想到圖論
    7月5日消息，據國外媒體報導，奧地利和美國的一個多學科研究小組日前把數學中的圖論用於生物進化研究，似乎為生物學家研究特定的種群結構如何影響自然選擇找到了方向為了找到更普遍的策略，諾瓦克把目光轉向了圖論。數學意義上的圖是表示項目集之間動態關係的結構：單個項目位於結構的頂點;每對項目之間的線條或邊緣描述它們之間的連接關係。在進化圖論中，個體生物佔據了每個頂點。隨著時間的推移，個體產生一個相同後代的概率是一定的，其可以取代相鄰頂點上的個體，但它也面臨著被下一代個體所取代的風險。這些概率以「權重」和頂點之間線的方向連接到結構中。
  • 專訪喬治亞理工宋樂教授:用強化學習為圖論組合優化問題尋找「元...
    專訪喬治亞理工宋樂教授：用強化學習為圖論組合優化問題尋找「元算法」大數據文摘作品，轉載要求見文末作者｜錢天培導讀：從交通優化、信息傳播優化、用戶網絡分析，組合優化這一傳統計算問題在日常應用中無處不在。然而，這類問題往往是NP難題（NP-hard），並需要大量的專業知識和試錯來解決。
  • 中國近百年來地表平均氣溫升高了1.1攝氏度
    國務院新聞辦公室29日發表的《中國應對氣候變化的政策與行動》白皮書指出，據中國氣象局發布的最新觀測結果顯示，中國從1908年到2007年的近百年來地表平均氣溫升高了1.1攝氏度。　　白皮書說，中國氣候變暖趨勢與全球的總趨勢基本一致。自1986年以來，中國已經歷了21個暖冬，2007年是自1951年有系統氣象觀測以來最暖的一年。