Content deleted Content added
m Reverted 2 edits by 240D:1A:7FC:9200:B5DD:CAFB:4B1F:62B2 (talk) to last revision by JayBeeEll |
No edit summary |
||
Line 74:
=== Mixed graph ===
{{main|Mixed graph}}
[[File:Example of simple mixed graph.jpg|thumb|160px|A simple mixed graph]]
A ''mixed graph'' is a graph in which some edges may be directed and some may be undirected. It is an ordered triple {{math|1=''G'' = (''V'', ''E'', ''A'')}} for a ''mixed simple graph'' and {{math|1=''G'' = (''V'', ''E'', ''A'', ''ϕ{{sub|E}}'', ''ϕ{{sub|A}}'')}} for a ''mixed multigraph'' with {{mvar|V}}, {{mvar|E}} (the undirected edges), {{mvar|A}} (the directed edges), {{mvar|ϕ{{sub|E}}}} and {{mvar|ϕ{{sub|A}}}} defined as above. Directed and undirected graphs are special cases.
=== Weighted graph ===
[[File:Weighted_network.svg|thumb|240px|A weighted graph with ten vertices and twelve edges]]
A ''weighted graph'' or a ''network''<ref>{{Citation | last=Strang | first=Gilbert | title=Linear Algebra and Its Applications | publisher=Brooks Cole | edition=4th | year=2005 | isbn=978-0-03-010567-8 }}</ref><ref>{{Citation | last=Lewis | first=John | title=Java Software Structures | publisher=Pearson | edition=4th | year=2013 | isbn=978-0133250121 | page=405 }}</ref> is a graph in which a number (the weight) is assigned to each edge.<ref>{{cite book|last1=Fletcher|first1=Peter|last2=Hoyle|first2=Hughes|last3=Patty|first3=C. Wayne|title=Foundations of Discrete Mathematics|year=1991|publisher=PWS-KENT Pub. Co.| ___location=Boston| isbn=978-0-53492-373-0| pages=463 | edition=International student|quote=A ''weighted graph'' is a graph in which a number ''w''(''e''), called its ''weight'', is assigned to each edge ''e''.}}</ref> Such weights might represent for example costs, lengths or capacities, depending on the problem at hand. Such graphs arise in many contexts, for example in [[shortest path problem]]s such as the [[traveling salesman problem]].
| |||