[理工] DS 圖形

[kiwidoit (噗嚕噗嚕)]

(1) 交大資工

An acyclic graph is a directed graph without cycles. No acyclic graph with

n vertices can have more that ___ edges.

(2) 元智資工-軟設

一個n個點有向圖，請問其最多具有多少個有向邊?

為什麼答案是n(n-1)?

(3) 99成大電機

In browsing web pages over Internet, if a web page is thought as a tree node

which has hyperlinks connecting to other pages as its children nodes, then

the web pages form a tree structure.

為什麼答案是False?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.123.175.231
推 gskman:2）n node每個node有n-1條邊n*(n-1)
→ gskman:3)可能有cycle
→ gskman:1) n-1
→ kiwidoit:他第一題答案給n(n-1)/2，所以他答案有錯囉@@
→ kiwidoit:忘了有向邊可以<-跟-> XD，感謝g大的解答!!
→ Byzantin:(1) n-1是undirect的答案吧，n(n-1)/2的話n=3好像就不對
→ kiwidoit:那答案到底是= =?
推 show8822:第一題應該是n-1沒錯