logo Use CA10RAM to get 10%* Discount.
Order Nowlogo
(5/5)

What is a Graph? how highly connected is an entity within a network? What is an entity's overall importance in a network ?

INSTRUCTIONS TO CANDIDATES
ANSWER ALL QUESTIONS

What is a Graph?

  • A graph is a data structure representing connections between items
    • We're storing values with the potential for connections between any or all elements
  • Examples of graphs in everyday life:
    • PERT charts
    • Flow charts
  • Examples in computer science
    • Networks
    • Social Network diagrams
    • Executing a makefile

 

Social Networks

Using Social Network Analysis, you can answer:

  • How highly connected

is an entity within a network?

  • What is an entity's

overall importance in a network?

  • How central is an entity within a network?
  • How does information

flow within a network?

Makefiles     

How make Works

  • Construct the dependency graph from the target and dependency entries in

the makefile      

  • Do a topological sort to determine an order in which to construct
  • For each target visited, invoke the commands if the target file does not exist or if any dependency file is newer
    • Relies on file modification

dates

Set Theory

  • A set is any collection of objects, e.g. a set of vertices
  • The objects in a set are called the elements of the set

 

  • Repetition and order are not important
    • {2, 3, 5} = {5, 2, 3} = {5, 2, 3, 2, 2, 3}

 

  • Sets can be written in predicate form:
    • {1, 2, 3, 4} = {x : x is a positive integer less than 5}
  • The empty set is {} = 0, all empty sets are equal

 

Elements and Subsets

  • x ∈ A means “x is an element of A”
    • x ∈ A means “x is not an element of A”

 

  • A ⊆ B means “A is a subset of B”
    • x ⊆ A means “x is not a subset of A”

 

  • If A ⊆ B and A ≠ B…

A is a proper subset of B and we write A ⊂                                                                               B

  • A ⊆ A for every set A
    • Every set is a subset of itself

Subsets

  • If A ⊆ B and B ⊆  C then A ⊆  C
  • If A ⊆ B and B ⊆ A then A = B

 

  • The empty set is a subset of every set:

⊆ A for any A

 

  • The subsets of A ={1, 2, 3} are:

 

,{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}

(Sometimes called the powerset of A, P(A) )

Operations on Sets

  • Union
    • A ∪ B = { x : x ∈ A or x ∈ B }

 

  • Intersection
    • A ∩ B = { x : x ∈ A and x ∈ B }

 

  • Universal Set
    • All sets under consideration will be subsets of a background set, called the Universal Set, U
  • Complement
    • A' = { x : x ∈ U and x ∈ A }

Example

  • Let:
    • U = {a, b, c, d, e, f}
    • A = {a, c}
    • B = {b, c, f}
    • C = {b, d, e, f}

 

  • Then:
    • B ∪ C = {b, c, d, e, f}
    • A ∩ (B ∪ C) = {c}
    • A' = {b, d, e, f}

= C

  • A' ∩ (B ∪ C) = C ∩ (B ∪  C) = {b, d, e, f} = C
(5/5)
Attachments:

Expert's Answer

540 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

540 Times Downloaded

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Atharva PatilComputer science

761 Answers

Hire Me
expert
Chrisantus MakokhaComputer science

510 Answers

Hire Me
expert
AyooluwaEducation

811 Answers

Hire Me
expert
RIZWANAMathematics

678 Answers

Hire Me

Get Free Quote!

395 Experts Online