Graph Glossary

From OSF Wiki
Jump to: navigation, search

This is a partial listing of graph-related terms.[1]

  • Half-edge graph: a unary edge (i.e., an edge that "connects" one vertex). It has limited practical application and is primarily discussed in mathematics.
  • Multi-graph: There are many situations in which it is desirable to have multiple edges between the same two vertices.
  • Simple graph: the prototypical graph, where an edge connects two vertices and no loops are allowed
  • Weighted graph: used to represent strength of ties or transition probabilities
  • Vertex-labeled graph: Most every graph makes use of labeled vertices (e.g., an identifier).
  • Semantic graph: used to model cognitive structures such as the relationship between concepts and the instances of those concepts [2]
  • Vertex-attributed: used in applications where it is desirable to append non-relational metadata to a vertex
  • Edge-labeled graph: used to denote the way in which two vertices are related (e.g., friendships, kinships, etc.)
  • Directed graph: orders the vertices of an edge to denote edge orientation
  • Hypergraph: generalizes a binary edge whereby an edge connects an arbitrary number of vertices [3]
  • Undirected graph: the typical graph that is used when the relationship is symmetric (e.g., friendship)
  • Resource description framework graph: a graph standard developed by the World Wide Web consortium that denotes vertices and edges by uniform resource identifiers [4]
  • Edge-attributed graph: used in applications where it is desirable to append non-relational metadata to an edge
  • Pseudo graph: used to denote a reflexive relationship
  1. Drawn from Marko A. Rodriguez and Peter Neubauer, 2010. Constructions from Dots and Lines, ASIS&T Bulletin, August/September 2010.