歡迎來到 財團法人台北市九章數學教育基金會
首頁 新聞區 討論區 檔案下載
重要公告

2019 澳洲AMC數學能力檢定


2019年國際中小學數學能力檢測(IMAS)


第22屆小學數學世界邀請賽(PMWC 2019,香港)與2019國際小學數學競賽(SAIMC 2019,南非Durban市)


2019青少年數學國際城市邀請賽(SAIMC 2019,南非Durban市))


2019年國際小學數學及自然科學奧林匹亞 (IMSO 2019,越南 Hanoi市)


2019國際青少年數學奧林匹亞 (ITMO 2019,印度 Lucknow市)

歷史公告

澳洲AMC數學能力檢定

2018 澳洲AMC

2017 澳洲AMC


國際中小學數學能力檢測(IMAS)

IMAS 2018

IMAS 2017


小學數學競賽

小學數學世界邀請賽與國際小學數學競賽

PMWC 2018與BIMC 2018

PMWC 2017與InIMC 2017

國際小學數學及自然科學奧林匹亞(IMSO)

IMSO 2018

IMSO 2017


中學數學競賽

青少年數學國際城市邀請賽

BIMC 2018

InIMC 2017

國際青少年數學奧林匹亞(ITMO )

ITMO 2017

ITMO 2015

國際青少年數學家會議(IYMC )

IYMC 2016

越南河內數學邀請賽(HOMC )

HOMC 2019


欲查詢其餘歷史公告,可利用首頁右側之關鍵字搜尋功能
目前並未有最新新聞!
主選單
· 回首頁
· 新聞區
· 討論區
· 檔案下載
· 網站連結
· 電子相薄
· 夥伴網站
· 精華文章
/  討論區主頁10
   /  高中
      /  Oriented graphs
限會員
發布者內容列
訪客








 Oriented graphs

Arrows are placed on the edges of a connected graph so that for any
vertex the numbers of "incoming" and "outgoing" edges are equal. Prove that one
can reach each vertex from any other by moving along the arrows

 2012-07-30 00:41
gkw0824usa
Just can't stay away



註冊日: 2004-07-28
發表數: 143
University of Texas at Austin

 Re: Oriented graphs

Let us rephrase your claim:
For a weakly connected digraph G=(V,E) for each vertex we have the same number of outgoing edges and incoming edges. Show that G is strongly connected.

My approach to this problem is induction:

Base case: |V| =1 is straight forward.
|V| = 2 since G is connected, there must exist at least 2 edges going opposite directions between the two vertices v_1 and v_2. Done.
Inductive Step:
Now suppose the claim holds true for |V|=n so we have a strongly connected graph G_n = (V,E). now we add an additional vertex v_n+1 so that V'=V+v_n+1. There must then be at least one incoming edge from G_n to v_n+1 and one outgoing edge from v_n+1 to G_n since we need the new graph to be connected and also fulfilling the equal property. WLOG let us assume (v_1,v_n+1) and (v_n+1,v_2) are the new edges which forms E'. There may be additional edges, but for our purposes they are insignificant. Now for any vertex i,j in V, there exists a Path P(i,j) that takes i to j according to our hypothesis. in order for i to get to the new node v_n+1, we take the path P(i,v_1)+(v_,n+1). Similarly, if we want to get from v_n+1 to any node j, we apply (v_n+1,v_2)+P(v_2,j). Thus the new Graph G_n+1=(V',E') is also strongly connected.
Q.E.D.

Do let me know if you see any flaws in the proof.


_________________
Atra esternī ono thelduin
Mor'ranr līfa unin hjarta onr
Un du evarīnya ono varda.

May good fortune rule over you
Peace live in your heart
And the stars watch over you.

 2012-10-03 23:45個人資料
gkw0824usa
Just can't stay away



註冊日: 2004-07-28
發表數: 143
University of Texas at Austin

 Re: Oriented graphs

引文:

now we add an additional vertex v_n+1 so that V'=V+v_n+1. There must then be at least one incoming edge from G_n to v_n+1 and one outgoing edge from v_n+1 to G_n since we need the new graph to be connected and also fulfilling the equal property.


I wasn't thinking straight. This line doesn't make any sense so this proof doesn't work. I'll see if I can get something going tomorrow. Gotta go to bed now.


_________________
Atra esternī ono thelduin
Mor'ranr līfa unin hjarta onr
Un du evarīnya ono varda.

May good fortune rule over you
Peace live in your heart
And the stars watch over you.

 2012-10-04 00:04個人資料
gkw0824usa
Just can't stay away



註冊日: 2004-07-28
發表數: 143
University of Texas at Austin

 Re: Oriented graphs

currently working on if partitioning the graph into strongly connected components would work.


_________________
Atra esternī ono thelduin
Mor'ranr līfa unin hjarta onr
Un du evarīnya ono varda.

May good fortune rule over you
Peace live in your heart
And the stars watch over you.

 2012-10-04 13:39個人資料


九章數學出版社、九章數學基金會版權所有
本網頁各鍊結標題及鍊結內容歸原權利人所有
Copyright 2000 ~2004九章數學出版社、九章數學基金會
本網站內所有文字及資料版權均屬九章所有,未經書面同意之商業用途必究
This web site was made with XOOPS, a web portal system written in PHP.
XOOPS is a free software released under the GNU/GPL license.

TW XOOPS Official WebsiteFreeBSD Official WebsiteApache Official Website

Powered by XOOPS 1.3.10 © 2002 The XOOPS Project