Digraphs & orientations.html (2867B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-0.7313327193260193"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:06:41 +0000"/><meta name="latitude" content="52.3345077115161"/><meta name="longitude" content="4.866741210123743"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 23:04:21 +0000"/><title>Digraphs & orientations</title></head><body><div>Directed graphs:</div><ul><li><div>to convert graph to digraph, represent each edge with two equally weighted arcs</div></li><li><div>digraph D consists of sets V(D) vertices and A(D) arcs</div></li><li><div>arc <u,v> joins vertex u (tail) to head v</div></li><li><div>has indegree and outdegree, where the sum of all outdegrees is the same as the sum of all indegrees, which equals the number of arcs in D.</div></li><li><div>adjacency matrix is not symmetric</div></li><li><div>strict if ∀ u,v: (A[u,v]) ≤ 1 and A(u,u)=0</div></li><ul><li><div>in english: no duplicate edges between vertices, no loops</div></li></ul></ul><div><br/></div><div>Connectivity with digraphs:</div><ul><li><div>strongly connected: there is a directed path "there and back" between any two vertices</div></li><li><div>weakly connected: the underlying graph is connected (i.e. if all edges were made undirected, the graph would be connected)</div></li><li><div>strongly connected digraphs form strongly connected components</div></li><li><div>vertex v is reachable from u if there is a path (u,v)</div></li><li><div>algorithm for reachability:</div></li><ul><li><div>Rt(u) is the set of reachable vertices from u, found after t steps.</div></li><li><div>steps:</div></li><ol><li><div>Set t ← 0 and R<span style="vertical-align: sub;">0</span>(u) ← {u}</div></li><li><div>Construct set R<span style="vertical-align: sub;">t+1</span>(u) ← R<span style="vertical-align: sub;">t</span>(u) U<span style="vertical-align: sub;">v ∈ Rt(u)</span> N<span style="vertical-align: sub;">out</span>(v)</div></li><li><div>If R<span style="vertical-align: sub;">t+1</span>(u) = Rt(u), stop: R(u) ← R<span style="vertical-align: sub;">t</span>(u). Else, increment t and repeat step 2.</div></li></ol></ul></ul><div><br/></div><div>Orientations</div><ul><li><div>orientation of a simple graph is a digraph where you give every edge a direction</div></li><li><div>there is strongly connected orientation iff λ(G) ≥ 2</div></li></ul><div><br/></div></body></html>