b'\n_START_ARTICLE_\nRiktad graf\n_START_PARAGRAPH_\nEn riktad graf inom grafteorin \xc3\xa4r en variant av graf vars b\xc3\xa5gar (kanter) har en definierad riktning mellan de tv\xc3\xa5 noder som b\xc3\xa5gen f\xc3\xb6rbinder, b\xc3\xa5gen \xc3\xa4r s\xc3\xa5 att s\xc3\xa4ga enkelriktad. \xc3\x84ven de f\xc3\xb6rkortade beteckningarna rigraf och digraf (efter engelska directed graph) anv\xc3\xa4nds. Via den kant som f\xc3\xb6rbinder A med B, kan man bara g\xc3\xa5 fr\xc3\xa5n nod A till nod B, eller fr\xc3\xa5n B till A, inte \xc3\xa5t b\xc3\xa5da h\xc3\xa5llen. F\xc3\xb6r att kunna g\xc3\xa5 \xc3\xa5t b\xc3\xa5da h\xc3\xa5llen beh\xc3\xb6vs tv\xc3\xa5 kanter, en fr\xc3\xa5n A till B och en fr\xc3\xa5n B till A.\n_START_SECTION_\nFormell definition och terminologi\n_START_PARAGRAPH_\nMatematiskt sett \xc3\xa4r en riktad graf ett par (N,B) best\xc3\xa5ende av en nodm\xc3\xa4ngd N och b\xc3\xa5gm\xc3\xa4ngd B. B \xc3\xa4r en delm\xc3\xa4ngd av alla ordnade par av element i N, med andra ord \xc3\xa4r alla element i B par p\xc3\xa5 formen (x, y) d\xc3\xa4r x och y b\xc3\xa5da \xc3\xa4r element i N. Ordningen p\xc3\xa5 paret best\xc3\xa4mmer riktningen p\xc3\xa5 b\xc3\xa5gen, (x,y) \xc3\xa4r en b\xc3\xa5ge fr\xc3\xa5n x till y._NEWLINE_Givet en b\xc3\xa5ge b=(x,y) \xc3\xa4r den inverterade b\xc3\xa5gen till b b\xc3\xa5gen (y,x). Om det f\xc3\xb6r varje b\xc3\xa5ge i en graf \xc3\xa4r s\xc3\xa5 att \xc3\xa4ven den inverterade b\xc3\xa5gen finns i grafen kallas grafen symmetrisk och kan ers\xc3\xa4ttas med en vanlig, oriktad, graf._NEWLINE_En orienterad graf \xc3\xa4r en riktad graf erh\xc3\xa5llen ur en oriktad graf genom att man tar de oriktade b\xc3\xa5garna i den oriktade grafen och ger dem en riktning. Skillnaden mellan en orienterad graf och en allm\xc3\xa4n ritkad graf \xc3\xa4r att i en orienterad graf kan inte b\xc3\xa5de en b\xc3\xa5ge och dess invers finnas med._NEWLINE_En viktad digraf \xc3\xa4r en riktad graf med vikter p\xc3\xa5 b\xc3\xa5garna, liknande en vanlig viktad graf.\n_START_SECTION_\nUtgrad och ingrad\n_START_PARAGRAPH_\nGivet en nod n i en riktad graf \xc3\xa4r nodens ingrad antalet b\xc3\xa5gar som g\xc3\xa5r till noden och dess utgrad \xc3\xa4r antalet b\xc3\xa5gar som g\xc3\xa5r fr\xc3\xa5n noden._NEWLINE_Ingraden f\xc3\xb6r en nod n betecknas ofta \\deg^-(n) och utgraden \\deg^+(v). En nod med \\deg^-(v)=0 kallas f\xc3\xb6r en k\xc3\xa4lla och en nod med \\deg^+(v) = 0 kallas avlopp.'