Scribd Logo
Upload

Welcome to Scribd!

  • 78 views

    Graph Terminology

    Uploaded by

    Liew Soung Yue
    A graph consists of a set of vertices and edges. An edge connects two vertices, making them neighbors or adjacent. A graph is undirected if edges are bidirectional, and directed if edges only go one way. A path is a sequence of edges from one vertex to another. A graph is connected if there is a path between all vertex pairs. Subgraphs, trees, and cuts are important graph concepts used in network design problems.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    Graph Terminology

    Uploaded by

    Liew Soung Yue
    78 views3 pages
    A graph consists of a set of vertices and edges. An edge connects two vertices, making them neighbors or adjacent. A graph is undirected if edges are bidirectional, and directed if edges only go one way. A path is a sequence of edges from one vertex to another. A graph is connected if there is a path between all vertex pairs. Subgraphs, trees, and cuts are important graph concepts used in network design problems.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    A graph consists of a set of vertices and edges. An edge connects two vertices, making them neighbors or adjacent. A graph is undirected if edges are bidirectional, and directed if edges only go one way. A path is a sequence of edges from one vertex to another. A graph is connected if there is a path between all vertex pairs. Subgraphs, trees, and cuts are important graph concepts used in network design problems.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    78 views3 pages

    Graph Terminology

    Uploaded by

    Liew Soung Yue
    A graph consists of a set of vertices and edges. An edge connects two vertices, making them neighbors or adjacent. A graph is undirected if edges are bidirectional, and directed if edges only go one way. A path is a sequence of edges from one vertex to another. A graph is connected if there is a path between all vertex pairs. Subgraphs, trees, and cuts are important graph concepts used in network design problems.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 3

    Graph Terminology

    1. A graph, G, is composed of vertex set, V, and edge set, E. This can be


    expressed as G = (V, E).

    2. Vertices ~ nodes, edges ~ links.

    3. A link between node i and node k can be denoted by ej = (i, k). In this
    case, nodes i and k are said to be adjacent, or they are neighbors.

    4. A link could be unidirectional such that the order of nodes does matter.
    Such a link is referred to as an arc which can be denoted by aj = [i, k].

    5. A graph with links is called an undirected graph while one with arcs is
    called a directed graph.

    6. If two links share the same pair of nodes, then they are called parallel
    links. A graph with parallel links is called a multigraph.

    7. If a link connects a node to itself, then it is called a self loop. (See


    Figure 3.2 for example)

    8. A graph without parallel links or self loops is called a simple graph.

    9. A path in a network is a sequence of links which begins at some node,


    s (which is called source), and ends at some node, t (which is called
    destination or sink). Such a path is also referred to as s,t-path.

    10. A path can be directed or undirected, but the order of links does matter.

    11. A path is said to be simple if a node appears no more than once in the
    path, i.e., no loop.

    12. If s is the same as t, the path is called a cycle, and if each intermediate
    node appears no more than once, the cycle is called a simple cycle. (See
    Example 3.1 and Figure 3.1)

    13. A graph is connected if there is at least one path between every pair of
    nodes.
    14. The sets of nodes with paths to one another are connected
    components, or more simply, components.

    15. If links are bidirectional, the nodes in a component form an equivalent


    class, where
    a. i ~ i; (by definition)
    b. if i ~ j, then j ~ i ; (because links are bidirectional)
    c. if i ~ j and j ~ k, then i ~ k (trivial).

    16. A directed graph with a directed path from every node to every other
    node is called strongly connected.

    17. A set of nodes with directed paths from any node to any other node is
    called a strongly connected component. (See Example 3.2 and Figure
    3.3)

    18. Given a graph, G = (V, E), H is a subgraph of G if H = (V’, E’), where


    V’ is a subset of V and E’ is a subset of E.

    19. A spanning tree is a connected graph without cycles. More simply we


    just refer such a graph to as a tree.

    20. If the graph is not necessarily connected, it is referred to as a forest.


    21. Spanning trees have the following interesting properties which make
    them useful in designing communications networks:
    a. They are minimally connected, that is, no subset of the edges
    forms a connected graph. Thus, a tree would be the optimal
    solution when designing a connected network of minimum cost.
    b. There is exactly one path between every pair of nodes in a tree,
    thus, routing problem is trivial in trees.

    22. If a graph has N nodes, any tree spanning the nodes has exactly N-1
    nodes. In fact, any forest with k components contains exactly N-k edges.

    23. A set of edges, whose removal disconnects a graph, is called a


    disconnecting set.

    24. A disconnecting set which partitions the set of nodes into two sets, X
    and Y, is called an X-Y cutset.
    25. An X-Y cutest is called a minimal cutset if it contains minimum number
    of edges to partitions nodes into sets X and Y. That is, a minimal cutset
    has no subsets that are also a cutset. (See Example 3.3 and Figure 3.4)

    26. In a tree, any edge is a minimal cutset.

    27. A minimal set of nodes whose removal partitions the remaining nodes
    into two sets is called a cut. (See Example 3.3 and Figure 3.4)

    You might also like