Trong một số vấn đề mối quan hệ giữa các đối tượng không phải là đối xứng. Đối với các trường hợp này, chúng ta cần đồ thị chỉ đạo, các cạnh được định hướng từ một đỉnh khác. Ví dụ, hãy xem xét một bản đồ của một thị trấn nhỏ. Bạn có thể làm cho đường phố một chiều, và vẫn có thể lái xe từ một nhà ở khác (hoặc ra khỏi thị trấn) | 6 Directed Graphs Digraphs In some problems the relation between the objects is not symmetric. For these cases we need directed graphs where the edges are oriented from one vertex to another. As an example consider a map of a small town. Can you make the streets one-way and still be able to drive from one house to another or exit the town . Definition. a digraph or a directed graph D Vd- Ed consists of the vertices Vd and directed edges Ed c Vd X Vd without loops w . We still write w for m v but note that now IJC vu. For each pair e uv define the inverse ofc as e l vu v u . Note that eE Ed does not imply e-1 G Ed. Definition. Let 4 be a digraph. Then 4 is its subdigraph if VA c VD and EAQ ED induced subdigraph A Z X if 4 X and EA Ed n X X X . The underlying graph U D of a digraph D is the graph on Vd such that if e G Ed then the undirected edge with the same ends is in w A digraph 4 is an orientation of a graph G if G u D and e G Ed implies e Ạị Ed. In this case 4 is said to be an oriented graph. Definition. Let 4 be a digraph. A walk w 6162 . e u - V of U D is a directed walk if 6j G Ed for all i E 1 k Similarly we define directed paths and directed cycles as directed walks and closed directed walks without repetitions of vertices. The digraph 4 is di-connected if for all nA V there exist directed paths u A V and V A u. The maximal induced di-connected subdigraphs are the di-components ofD. Digraphs 84 Note that a graph G U D might be connected although the digraph D is not diconnected. Definition. The indegree and the outdegree of a vertex are defined as follows 4 u e G Ed I e zv dg u e G ED I e vz . We have the following handshaking lemma. You offer and accept a handshake. Lemma . Let D be a digraph. Then 4W ED . veD veD Directed paths The relationship between paths and directed paths is in general rather complicated. This digraph has a path of length five but its directed paths are of length one. There is a nice connection between the lengths of .
