Flashcards in Decision: Graphs and Networks: Definitions Deck (20)

Loading flashcards...

1

## Define a walk

### A route through a graph along edges from one vertex to the next

2

## Define a Path

### A walk in which no vertex is visited more than once

3

## Define a Trail

### A walk in which no edge is visited more than once

4

## Define a Cycle

### A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

5

## Define a Hamiltonian Cycle

### A cycle that includes every vertex

6

## Define a Loop

### An edge that starts and finishes at the same vertex

7

## Define a Simple Graph

### A graph in which there are no loops and there is at most one edge connecting any pair of vertices

8

## Define a '2 vertices connected'

### Two vertices are connected if there is a path between them.

9

## Define a Directed Graph (Digraph)

### A graph where the edges are directed

10

## Define Euler's handshaking Lemma

### In any undirected graph, the sum of the degrees pf the vertices = 2* the number of edges. As a consequence the number of odd nodes must be even = Euler's handshaking Lemma

11

## Define a Tree

### A connected graph with no cycles

12

## Define a Spanning tree

### A spanning tree of a graph is a subgraph which includes all the vertices of the original graph and is also a tree

13

## Define a Complete graph

### A graph in which every vertex is directly connected by a single edge to each of the other vertices

14

## Define Isomorphic graphs

### Graphs which show the same information but are drawn differently

15

## Define a Adjacency matrix

### A matrix in which every entry describes the number of arcs joining the corresponding vertices

16

## Define a Distance matrix

### A matrix in which the entries represent the weight of each arc

17

## A graph consist of points [ ] which are connected by lines [ ]

###
Vertices/Nodes

Edges/Arcs

18

## Define Weighted Graph / Network

### A graph that has a number associated with each edge

19

## Define Subgraph

### A graph, each of whose vertices belongs to the original graph and each of whose edges belong to the original graph. It is part of the original graph

20