algorithm - Graph Connectivity Proof -


suppose have adjacency matrix g representing n-node graph. g[i, j] 1 if there's edge j , 0 otherwise. can think of each entry turned on slip of paper 1 or 0 on it.

my text claims lower bound on number of times need query matrix determine if graph connected n * (n-1) / 2. i'm bit confused proof of this.

proof: here strategy adversary: when algorithm asks flip on slip of paper, return 0 unless force graph disconnected.

1) seems imply in cases, if return 0, it's impossible add edges later lead path u v. surely graph can still connected if return 0 above...right?

claim: maintain invariant y un-asked pair (u, v) graph revealed far has no path u v

proof: suppose there path u v. can remove last edge (u', v') revealed on path. have answered 0 , kept same connectivity in graph having edge (u, v). contradicts definition of our adversary strategy.

end of proof: suppose there algorithm finished without examining every slip of paper. consider unasked pair (u, v). if algorithm claims graph connected, show all-zeroes remaining unasked edges and means there no path u v, algorithm wrong.

2. explain italics? i'm not seeing connection...

on other hand, if algorithm says disconnected, show all-ones remaining edges , algorithm wrong definition of our adversary strategy.

3. couldn't graph still disconnected if show ones?

thanks!

  1. suppose have four-node graph. if algorithm has queried , gotten "0" answers 13 , 14, , asks 12, if answer "0", means graph cannot connected, because 1 not connected 2 (there's no direct path, , 1 has no other possible connection).

  2. at given time, can think of edge being "yes", "maybe", or "no". edges "maybes". whenever algorithm asks edge, becomes "yes" or "no". graph yes , maybe edges connected input consistent observations. graph yes edges least connected input consistent observations. algorithm can return when these graphs have same connectivity status.


-

Comments

Post a Comment

Popular posts from this blog

swift - Button on Table View Cell connected to local function -

i have table view cell loaded data parse request. loads "friend requests", showing requesting friends name , 2 buttons, "accept" , "reject" here cellforrowatindexpath func: func tableview(tableview: uitableview, cellforrowatindexpath indexpath: nsindexpath) -> uitableviewcell { let cell:notifications_jlr_cell = self.tableview.dequeuereusablecellwithidentifier("cell") as! notifications_jlr_cell cell.txtrequestdesc.text = searchresults[indexpath.row].requesteename + " has requested friend" cell.btnapprove_outlet.addtarget(self, action:selector("approve"), forcontrolevents: uicontrolevents.touchupinside) return cell } the table loads fine, , addtarget line, once "approve" button clicked, runs func: func approve() { println("approve") } however, when fetching parse data, have set in array, objectid friend request, want refer in approve() function how can pass objectid ...
Read more

dns - Dokku server hosts two sites with TLD's, both domains are landing on only one app -

i have 2 simple dokku sites on 1 server. first static html site, , second simple rails app. each app has own tld. sake of argument give them domains: static.com , rails.com. ive used dokku domains plugin set both naked , 'www' domains each site. domain names purchased , setup through namecheap the namecheap domains each have 2 entries: @ | http://www.static.com | url redirect www | static.server.com | cname(alias) @ | http://www.rails.com | url redirect www | rails.server.com | cname(alias) i encountered this issue on dokku github page indicate can overcome using naked domain app name when creating original git remote. git remote add dokku dokku@server.com:static.com however, issue closed 2 years ago, , same result seems accomplished domains plugin. im wondering if should restart point both apps? so far above steps has resulted in traffic both domains being sent static.com. has encountered before? t...
Read more

c# - ajax - How to receive data both html and json from server? -

i have referenced this topic , doesn't solve problem. i'm using mvc 5 c#. have used code receive data server data type json . $.ajax({ url: "/mycontroller/myaction", type: "post", datatype: "json", success: function (data) { if (data.result) { alert('successfull'); } else { alert(data.ex); } } }); and controller code: [httppost] public actionresult myaction() { try { return json(new { result = "true", ex = "" }); } catch (exception e) { return json(new { result = "false", ex = e.message }); } } i use way data type html: $.ajax({ url: "/mycontroller/myaction", type: "post", datatype: "html", success: function (data) { $(".mydiv").append(data); } }); and controller should be: [httppost] public actionresult myaction() { return partialview("_...
Read more