Flashcards in Graphs and trees Deck (12):

1

## Define an undirected graph

### A graph where the relationship between vertices is two way

2

## Define a directed graph

### A graph where the relationship between vertices i one way

3

## What are the important parts of graphs and trees?

###
Vertex/vertices - an object in a graph (also know as a node)

Arc - the join/relationship between two nodes

4

## What is the difference between a weighted and an unweighted graph?

###
A weighted graph has values between/for the node.

An unweighted graph has no values for each arc.

5

## List some uses for graphs

###
Human networks - Each node is a person and each arc is the relationship between them

Transport networks - All locations on the networks are nodes on the graph and the arcs the routes between them

6

## Define adjacency list

### A data structure that stores a list of nodes with their adjacent nodes

7

## Define adjacency matrix

### A data structure set up as a two dimensional array or grid that shows whether there is an edge between each pair of nodes

8

## Adjacency list VS adjacency matrix

###
Adjacency list;

-Only stores data where there is an edge. less storage space

-It has to be tested every time to see if two nodes connect. Increases processing time

Adjacency matrix;

-Stores values for every combination. Takes up a lot of space

-Adjacencies can be identified more quickly

9

## Define tree in relation to computing

### a data structure similar to a graph but with no loops

10

## What are the parts of a tree in relation to computing?

###
Node - An object on the graph

Edge - A join or relationship between two nodes

Root - The starting node from which the whole data structure stems off

Parent - A type of node on the tree with further nodes below it

Child - A node on the tree that has more node above it

Leaf - A node that doesn't have any node beneath it

11

## What is a binary search tree?

### A type of tree where each parent node can only have two children

12