lecture 1: graph theory

graph

a way of specifying relationships among a collection

networks stress the importance of (A) over (B)

A. interactions between items
B. individual characteristics

relationships in a graph are represented by…

edges/links

collections of items in a graph are represented by…

nodes

an undirected relationship is…

symmetric

a directed relationship is…

asymmetric

what is the symmetric relationship between A and B in a social network?

A is B’s friend and B is A’s friend

what is the asymmetric relationship between A and B in a social network

A follows B, but B may not follow A

degree

number of connections/edges a node has to other nodes

in a network of n nodes and m edges, the minimum possible number of degrees is…

0

in a network of n nodes and m edges, the maximum possible number of degrees is…

n-1

a degree of 0 means that…

the network contains only one node/the node isn’t connected to anything else

a degree of n - 1 (where n is the number of nodes) means that…

the node is connected to every other node

in a network of n nodes and m edges, the sum of degrees is…

2m

every time an edge is added, the sum of degrees changes by…

increases by 2

the number of edges can be found by…

dividing the sum of degrees by 2

in order to exist, the sum of degrees must be…

even

path

a sequence of nodes with each consecutive pair connected by an edge

length of a path

number of steps it contains from beginning to end

distance

shortest path between two nodes

a graph is considered connected if…

each pair of nodes can be connected through a path

connected components

parts of a graph that are not connected to each other but have their own network of connected nodes

two nodes can be connected through a path if…

they are in the same components