Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory Definitions

  1. Nov 18, 2003 #1

    My discrete math course has begun a section on graph theory. And I am hung up on some of the definitions. If someone is familiar with graph theory, I would appreciate it if some of these definitions could be reworded in another way. I will post the definitions we have taken so far and highlight the definitions with which I am having trouble.

    SIMPLE GRAPH - is formally defined as an ordered pair (V,E) where V is a nonempty set of elements called vertices and E is a set of two-element subsets e = {u,v} of V called edges.

    If some pairs of vertices have more than one edge joinging them, the result is called a MULTIGRAPH.
    If there are loops ( which are edges beginning and ending at the same vertex) the result is called a PSEUDOGRAPH.

    SUBGRAPH - of a graph is a set of vertices and edges, provided that all vertices incident with edges in the subgraph are included. In other words, a subgraph is a subset of the vertices and edges that itself forms a graph.

    Types of Subgraphs

    WALK - is a subraph that consists of a sequence of vertices and edges v0,e1,v1,e2,v2...en,vn such that for 1 =< i =< n, the edge ei joins vertices vi-1 and i.

    TRAIL - a walk in which no edges are repeated.

    PATH - a trail in which no vertices are repeated except perhaps for the first and last vertex.

    CIRCUIT - is a trail whose first and last vertices are the same.

    CYCLE - is a path whose first and last vertices are the same.

    Components of a Graph - Two vertices of a graph that are joined by a path are said to belong to the same component of the graph. If the whole graph is one component, then it is said to be connected.

    I definition of a walk is making more sense to me now that I have written it out here. But I still am having trouble with components of a graph and when a graph is connected.

    I also would like to know, if a graph is considered a multigraph, but it also has a loop, is it a multigraph or a pseudograph?

    Any help is appreciated. Thankyou.
  2. jcsd
  3. Nov 18, 2003 #2
    Draw a graph. Next to it, draw a completely different graph. You can regard the two together as subgraphs of a combined graph --- it's just that the combined graph is disconnected: it has two pieces. Each of those pieces is a (connected) component. Every node in one of the components is connected (directly, or indirectly through some path i.e. sequence of edges) to every other node in that component, but none of them are connected to any of the nodes in the other component.

    Well, a multigraph with a loop is still a multigraph. The definition of pseudograph was unclear: is it a (simple) graph with loops, or a multigraph with loops? Presumably, that's why you're asking the question ... you can't tell for sure from how the definition is worded.
  4. Nov 18, 2003 #3


    User Avatar
    Science Advisor
    Homework Helper

    A graph is connected if there is a trail/path betwteen every pair of vertices. "Connected" means what you think it ought to mean.

    A component is a maximal connected subgraph. If a graph is connected, then it only has one component -- the entire graph. Otherwise, each 'disconnected' piece is a component.

    How about both? They don't have to be exclusive.
    Last edited: Nov 18, 2003
  5. Nov 18, 2003 #4
    Thankyou Ambitwistor and NateTG.

    I think I understand now. I have to think about it a bit more but I believe I got it.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook