نمایش مبدأ برای گراف جهت‌دار

[[پرونده:Directed.svg|بندانگشتی|150px|یک گراف جهتدار]]
در ریاضیات و به‌طور خاص در [[نظریهٔ گراف]]، '''گراف جهت‌دار''' یا '''گراف سودار'''<ref>{{یادکرد فرهنگستان | مصوب=گراف سودار | بیگانه=directed graph | بیگانه در فارسی= | حوزه=ریاضی | دفتر=هفتم | بخش=فارسی | سرواژه=گراف سودار}}</ref> گرافی (مجموعه‌ای از گره‌ها که با یال‌ها به هم متصل شده‌اند) است که در آن به هر یال جهتی نسبت داده شده‌است. به زبان ریاضی، یک گراف جهت‌دار زوج مرتبی به صورت <math>G=(V,A)</math> است (گاهی به صورت <math>G=(V,E)</math> نیز نمایش داده می‌شود) که در آن<ref>Bang-Jensen & Gutin (2000). Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.</ref>
* V مجموعه‌ایست که اعضایش را رأس یا گره می‌نامند
* A مجموعه‌ای از زوج‌های مرتبی از رأس‌ها است که کمان، یال جهت‌دار، فلش یا گاهی یال نامیده می‌شوند (که در حالت اخیر مجموعهٔ متناظر را به جای A، با E نمایش می‌دهند).

گراف جهت دار با گراف معمولی عمده تفاوتشان در تعاریف یال هاست. یعنی [[زوج مرتب]] (a,b) با زوج مرتب (b ,a) تفاوتی در گراف معمولی یا بدون جهت ندارد و در حالت کلی تر آن را به شکل  ab می نویسیم ولی در گراف جهت دار زوج مرتب های (a,b) با (b,a) تفاوت دارد و نشان دهنده سوی یال است و نشان دهنده ی نحوه ی ارتباط بین این دو راس می باشد.

یک گراف جهت‌دار ساده نامیده می‌شود اگر هیچ طوقه و یال چندگانه‌ای نداشته باشد (یال‌های چندگانه یعنی یال‌هایی که ابتدا و انتهای یکسانی دارند). در یک گراف چندگانهٔ جهت‌دار یال‌ها تشکیل یک مجموعهٔ چندگانه (به جای مجموعه) از زوج‌های مرتب رأس‌ها می‌دهند و این گراف‌ها می‌توانند طوقه و یال چندگانه داشته باشند (طوقه یالی است که ابتدا و انتهایش رأس یکسانی است). در برخی متون، گراف جهت‌دار (بدون ذکر ویژگی ساده بودن) می‌تواند طوقه، یال چندگانه یا هر دو را داشته باشد.

== اصطلاحات پایه‌ای ==

یال <math>e=(x,y)</math> دارای جهت از <math>x</math> به <math>y</math> در نظر گرفته می‌شود. <math>y</math> ابتدا و <math>x</math> انتهای یال نامیده می‌شود. <math>y</math> را رأس مابعد مستقیم <math>x</math> و <math>x</math> را رأس ماقبل مستقیم <math>y</math> می‌نامند. اگر مسیری متشکل از یک یا چند یال رو به جلو از <math>x</math> به <math>y</math> وجود داشته باشد، به <math>y</math> رأس مابعد  <math>x</math> و به <math>x</math> رأس ماقبل <math>y</math> می‌گویند. به یال <math>(y,x)</math> معکوس یال <math>(x,y)</math> می‌گویند.

جهت‌دار کردن یک گراف سادهٔ بدون جهت یعنی نسبت دادن جهت به هر یال آن گراف. هر گراف جهت‌داری که به این طریق ساخته شود گراف جهت‌دار شده {{انگلیسی|oriented graph}} نامیده می‌شود. یک گراف جهت‌دار، یک گراف سادهٔ جهت‌دار شده‌است اگر و تنها اگر نه طوقه داشته باشد و نه حلقهٔ دوتایی (یال چندگانه). <ref>{{harvtxt|Diestel|2005}}, section 1.10.</ref>

گراف جهت‌دار وزن‌دار {{انگلیسی| weighted digraph}} گراف جهت‌داری است که به هر یالش وزنی نسبت داده شده‌است، درست مانند گراف بدون جهت وزن‌دار. در نظریهٔ گراف به گراف جهت‌دار با یال‌های وزن‌دار، شبکه {{انگلیسی|network}} می‌گویند.

ماتریس مجاورت {{انگلیسی|adjacency matrix}} یک گراف جهت‌دار (با طوقه و یال‌های چندگانه) ماتریسی دارای مقادیر صحیح است که سطرها و ستون‌هایش متناظر با گره‌ها هستند و در آن، مؤلفهٔ غیر قطری <math>a_{i,j}</math> تعداد یال‌ها از رأس i به رأس j و مؤلفهٔ قطری <math>a_{i,i}</math> تعداد طوقه‌های رأس i است. [[ماتریس مجاورت]] یک گراف جهت‌دار (با یکسان در نظر گرفتن جایگشت‌های سطرها و ستون‌ها) یکتاست. نمایش ماتریسی دیگری برای یک گراف، ماتریس وقوع{{انگلیسی|incidence matrix}} آن است. {{مدرک}}

== درجهٔ ورودی و درجهٔ خروجی ==
[[پرونده:DirectedDegrees.svg|بندانگشتی|چپ|200px|یک گراف جهت‌دار که رأس هایش به صورت (درجهٔ خروجی,درجهٔ ورودی) برچسب گذاری شده‌اند.]]
برای هر گره، تعداد رأس‌های ابتدایی مجاور، درجهٔ ورودی {{به انگلیسی|indegree}} و تعداد رأس‌های انتهایی مجاور، درجهٔ خروجی {{به انگلیسی|outdegree}} (در درخت‌ها ضریب انشعاب{{به انگلیسی|branching factor}}) نامیده می‌شود.

درجهٔ ورودی با <math>\deg^-(v)</math> و درجهٔ خروجی با <math>\deg^+(v)</math> نمایش داده می‌شود. رأس با <math>\deg^-(v)</math> صفر منبع {{به انگلیسی|source}} نامیده می‌شود (چون مبدأ همهٔ یال‌های متصل به خودش است) و به‌طور مشابه رأس با <math>\deg^+(v)</math> صفر چاه {{به انگلیسی|sink}} نامیده می‌شود.

رابطهٔ مجموع درجات بیان می‌کند که برای یک گراف جهت‌دار:

{{راست‌چین}}<math>\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |A|\,</math>{{پایان}}

اگر برای هر گرهٔ {{math|''v'' ∈ ''V''}}، <math>\deg^+(v) = \deg^-(v)</math> گراف را یک گراف جهت‌دار متعادل {{به انگلیسی|balanced digraph}} می‌نامیم. <ref>Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, {{ISBN|978-81-203-3842-5|en}}; Brualdi, Richard A. (2006), Combinatorial matrix classes, Encyclopedia of mathematics and its applications 108, Cambridge University Press, p. 51, {{ISBN|978-0-521-86565-4|en}}.</ref>

== همبندی گراف جهت‌دار ==

می‌گوییم یک گراف جهت‌دار ضعیفاً همبند است {{به انگلیسی|weakly connected}} (یا همبند است <ref>Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).</ref>) اگر گراف زمینهٔ آن (که با حذف جهت یال‌ها به دست می‌آید) یک گراف همبند باشد. می‌گوییم یک گراف جهت‌دار قویاً همبند است {{به انگلیسی|strongly connected}} (یا قوی است) اگر برای هر جفت رأس u و v مسیر جهتداری از u به v و مسیر جهتداری از v به u داشته باشد. مؤلفه‌های قوی {{به انگلیسی|strong components}}، زیرگراف‌های قویاً همبند ماکزیمال هستند.

== انواع گراف‌های جهت‌دار ==

گراف جهت‌دار G متقارن {{به انگلیسی|symmetric}} نامیده می‌شود اگر برای هر کمان متعلق به G، معکوس آن کمان نیز متعلق به G باشد. یک گراف جهت‌دار متقارن بدون طوقه معادل یک گراف بدون جهت است که با گذاشتن یک یال به جای هر جفت کمان معکوس هم به دست می‌آید (و بنابراین تعداد یال‌هایش نصف تعداد کمان‌های گراف اولیه است).

[[پرونده:Directed_acyclic_graph_2.svg|بندانگشتی|100px|یک گراف جهت‌دار سادهٔ بی‌دور]]
یک گراف جهت‌دار بی‌دور {{به انگلیسی|acyclic}} یا گراف بی‌دور جهت‌دار، گرافی جهت‌دار است که هیچ دور جهت‌داری ندارد. درخت‌های چندگانه {{به انگلیسی|multitrees}} (گراف‌هایی که در آن‌ها هیچ دو مسیر جهت‌داری که از یک گره شروع شده‌اند دوباره در یک گرهٔ مشترک تمام نمی‌شوند)، درخت‌های جهت‌دار {{به انگلیسی|oriented trees}} یا چنددرخت‌ها {{به انگلیسی|polytrees}} (گراف‌های جهت‌داری که از جهت‌دار کردن یال‌های یک گراف بدون جهت بی‌دور ساخته می‌شوند) و درخت‌های ریشه‌دار {{به انگلیسی|rooted trees}} (درخت‌های جهت‌داری که تمام یال‌های درخت بدون جهت زمینهٔ آن به سمت دور شدن از ریشه جهت‌دار شده‌اند) حالت‌هایی خاص از گراف‌های جهت‌دار بی‌دور هستند.

[[پرونده:4-tournament.svg|بندانگشتی|100px|تورنمنتی با چهار رأس]]
یک تورنمنت {{به انگلیسی|tournament}} گرافی جهت‌دار است که از جهت‌دار کردن همهٔ یال‌های یک گراف کامل {{به انگلیسی|complete graph}} بدون جهت به دست می‌آید.

در نظریهٔ گروه‌های لی، یک quiver، گرافی جهتدار است که دامنهٔ نمایش v (که به عنوان عملگر تعریف شده) می‌باشد (و بنابراین مشخص کنندهٔ شکل V است)؛ به ویژه شیئی از طبقهٔ عملگری '''FinVct'''<sub>K</sub><sup>F(Q)</sup> است که (F(Q طبقهٔ آزاد روی Q و تشکیل شده از مسیرهای Q است و '''FinVct'''<sub>K</sub> طبقهٔ فضای برداری با بعد متناهی روی میدان K است. نمایش‌های یک quiver رأس‌های آن را با فضاهای برداری و یال‌هایش (و در نتیجه مسیرهایش) را به‌طور سازگاری با تبدیلات خطّی بین این فضاها و تبدیل از طریق تبدیلات طبیعی برچسب‌گذاری می‌کند.

== جستارهای وابسته ==
* [[گراف]]
* [[نظریه گراف]]
* [[ریاضیات گسسته]]

== پانویس ==
{{چپ‌چین}}{{پانویس}}{{پایان}}

== منابع ==
{{چپ‌چین}}
*{{Citation
| last1=Bang-Jensen | first1=Jørgen
| last2=Gutin | first2=Gregory
| title=Digraphs: Theory, Algorithms and Applications
| publisher=[[اشپرینگر ساینس+بیزینس مدیا|Springer]]
| year=2000
| isbn=1-85233-268-9
| url=http://www.cs.rhul.ac.uk/books/dbook/
}}{{سخ}}(the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 {{ISBN|1-84800-997-6|en}}).
* {{citation
| last1=Bondy
| first1=John Adrian
| authorlink1=John Adrian Bondy
| last2=Murty
| first2=U. S. R.
| authorlink2=U. S. R. Murty
| title=Graph Theory with Applications
| year=1976
| publisher=North-Holland
| isbn=0-444-19451-7
| url=http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
| accessdate=22 مه 2014
| archiveurl=https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
| archivedate=13 آوریل 2010
| dead-url=yes
}}.
*{{Citation
| last=Diestel | first=Reinhard
| title=Graph Theory
| publisher=[[اشپرینگر ساینس+بیزینس مدیا|Springer]]
| year=2005
| edition=3rd
| isbn=3-540-26182-6
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
}} (the electronic 3rd edition is freely available on author's site).
*{{citation|last1=Harary|first1=Frank|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|title=Structural Models: An Introduction to the Theory of Directed Graphs|place=New York|publisher=Wiley|year=1965}}.
*{{citation | title=Number of directed graphs (or digraphs) with n nodes. | url=http://oeis.org/A000273}}
{{پایان}}
{{ساختمان داده‌ها}}
{{پانویس-نظریه گراف}}
[[رده:گراف‌های جهت‌دار]]
[[رده:نظریه گراف]]