Page History

...

• Directed vs Undirected:
  • Directed graphs (also called digraphs) consist of ordered pairs. The links in a directed graph are called arcs. Can use these to represent non-symmetric relations like "is the boss of" or "is attracted to"
  • Undirected graphs (also known simply as "graphs") consist of unordered pairs. They are used for the relations which are necessarily symmetric, such as "is the sibling of" or "lives with"
• Valued vs Non-Valued
  • In non-valued graphs, nodes are either connected or not. Either Sally and Bill are siblings, or they're not.
  • In valued graphs, the lines have values attached to represent characteristics of the relationships, such as strength, duration, capacity, flow, etc.
• Reflexive vs Non-Reflexive
  • Reflexive graphs allow self-loops. That is, a node can have a tie to itself. This is mostly useful when the nodes are collectivities. For example, if the nodes are cities and the ties represent phonecalls between people living in those cities, it is possible (a virtual certainty) that there will be ties from a city to itself.
• Multi-graphs
  • If more than one edge connects two vertices, this is a multigraph. In general, we do not use multigraphs, preferring to use either valued graphs (to represent the number of interactions between A and B) or wholly separate graphs (to represent substantively different relations, such as "does business with" and "is married to"
    

...

...