Scope of Network Models
Pipeline Design: Agar kisi ko Gulf of Mexico se gas supply karni ho, toh sabse kam kharche wali pipeline banane ka model use kiya jata hai.
Gulf of Mexico ek bara samundari hissa hai jo North America ke neeche mojood hai. Yeh America, Mexico aur Cuba ke darmiyan hai.
Yeh ek bara pani ka ilaqa hai jo Atlantic Ocean se connected hai.
Yahan par bohot zyada tel aur gas mojood hai, is wajah se yeh duniya ki economy ke liye important hai.
Is Gulf se America aur Mexico dono apni oil aur gas ki zaroorat poori karte hain.
Yeh bohot saari machliyon aur samundari zindagi ka bhi ghar hai.
ek bara talab ya dariya jo sirf ek mulk mein nahi, balki alag alag mulkon ko connect karta hai.
Shortest Route: Do shehron ke darmiyan sabse chhoti aur behtareen road ka pata lagana.
Maximum Flow: Agar Wyoming ke coal mines se Houston tak coal le jana ho, toh sabse zyada coal kis tareeke se bheja ja sakta hai.
Wyoming ke coal mines → Wyoming ek jagah hai America (USA) mein, jahan bohot zyada coal (koila) milta hai.
Houston → Houston ek bara shehar hai Texas, USA mein. Yahan bahut si factories aur power plants hain jo bijli banane ke liye coal (koila) istemal karte hain.
Project Scheduling: Koi construction project kab start aur kab complete hoga, iska schedule banane ke liye network model istemal hota hai.
Minimum Cost Flow: Oil fields se refineries tak tel le jane ka sabse sasta tareeqa dhoondhna.
In Problems Ko Solve Karne Ke Liye 4 Important Algorithms:
Minimal Spanning Tree – Kam se kam pipeline cost pe design karne ke liye.
Shortest-Route Algorithm – Do jagahon ke darmiyan sabse chhoti aur behtareen road dhoondhne ke liye.
Maximal-Flow Algorithm – Sabse zyada coal ya paani ek network se doosre tak le jane ke liye.
Critical Path Method (CPM) – Construction ya kisi bhi project ka best time schedule banane ke liye.
Network Definitions
A network consists of a set of nodes linked by arcs (or branches).
Nodes (also called vertices) and arcs (also called edges or branches)
Nodes are the points in the network (e.g., cities on a map, intersections in a road system, computers in a network).
Nodes (N): Yeh woh jagahain hain jahan se connections shuru ya khatam hotay hain. (Jaise shehr, road ke junctions, ya computer systems)
Arcs are the connections between nodes (e.g., roads connecting cities, cables connecting computers)
Arcs (A): Yeh woh rasty hain jo nodes ko jodtay hain. (Jaise shehron ke darmiyan roads, ya computers ke darmiyan cables)
The notation for describing a network is (N, A), where N is the set of nodes and A is the
set of arcs.
Agar ek network mein 5 nodes hain (1, 2, 3, 4, 5) aur unke darmiyan connections hain, toh hum isko is tarah likh saktay hain:
N={1,2,3,4,5} and A={(1,2), (1,3), (2,3), (2,5), (3,4), (3,5), (4,2), (4,5)}
Nodes (N): The example network has nodes labeled 1, 2, 3, 4, and 5. So, N = {1, 2, 3, 4, 5}.
Arcs (A): The connections are:
From node 1 to 2 (1, 2)
From node 1 to 3 (1, 3)
From node 2 to 3 (2, 3)
From node 2 to 5 (2, 5)
From node 3 to 4 (3, 4)
From node 3 to 5 (3, 5)
From node 4 to 2 (4, 2)
From node 4 to 5 (4, 5)
Thus, A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}
An arc is said to be directed or oriented if it allows positive flow in one direction and zero flow in the opposite direction. A directed network has all directed arcs. A path is a sequence of distinct arcs that join two nodes through other nodes regardless of the direction of flow in each arc. A path forms a cycle or a loop if it connects a node to itself through other nodes.
For example, the arcs (2,3), (3, 4), and (4,2) form a cycle.
Directed Arc (Oriented): A directed arc allows flow in only one direction. Think of a one-way street.
Directed Network: A network where all arcs are directed.
Path: A sequence of connected arcs that you can travel along to get from one node to another. The direction of the arcs doesn't matter when defining a path.
Example in Figure 6.1: 1 -> 3 -> 4 -> 2 is a path from node 1 to node 2.
Cycle (Loop): A path that starts and ends at the same node.
Example in Figure 6.1: 2 -> 3 -> 4 -> 2 is a cycle.
Flow in a Network
Associated with each network is a flow (e.g., oil products flow in a pipeline and automobile traffic flows in highways). In general, the flow in a network is limited by the capacity of its arcs, which may be finite or infinite.
Concept: Networks often represent the movement of something, called flow. This could be:
Oil in a pipeline
Traffic on roads
Data in a computer network
Capacity: Arcs have a capacity, which is the maximum amount of flow they can handle. This might be:
The diameter of a pipe for oil flow
The number of lanes on a road for traffic flow
The bandwidth of a cable for data flow
Finite or Infinite Capacity: Capacity can be limited (finite) or unlimited (infinite).
Network sirf connections ka naam nahi, balki kisi bhi cheez ka ek point se doosray tak pohanchna bhi iska aik hissa hai. Yeh cheezein ho sakti hain:
Tel pipelines ke andar
Road traffic
Data internet par
Har arc ki ek capacity hoti hai, yani woh kitni cheezon ko ek waqt mein guzarne de sakti hai. Jaise:
Pipeline ka diameter
Road ki lanes
Internet cable ki bandwidth
A connected network is such that every two distinct nodes are linked by at least one path.
A tree is a cycle-free connected network comprised of a subset of all the nodes, and a spanning tree is a tree that links all the nodes of the network.
Connected hota hai → Matlab, har node (point) ek doosre se connected hoti hai.
Cycle-free hota hai → Matlab, isme koi bhi aisi raah (path) nahi hoti jo ghoom phir ke wapas usi jagah le aaye.
Subset ka matlab hota hai kisi badi cheez ka ek chhota hissa.
Comprised of ka matlab hai mil kar bana hai.
Shajra (family tree) jisme dada se beta, phir beta se pota connected hai. Lekin koi bhi banda wapas dada se direct connected nahi hoga—yeh ek tree ka example hai.
Agar ek bara network hai jisme 10 nodes hain, toh ek tree sirf 5 ya 6 nodes ka chhota hissa (subset) ho sakta hai, jo aapas mein connected ho lekin koi ghoom phir kar wapas na aaye (cycle na ho).
Spanning Tree
Poore network (graph) ke sabhi nodes ko cover karta hai.
Koi cycle nahi hoti (jaise ek simple tree mein hoti hai).
Edges kam se kam hoti hain taa ke network connected rahe magar extra connections na hon.
Ek graph ke bohot saare different spanning trees ho sakte hain.
Agar ek spanning tree nikalna ho, toh asal graph ke sabhi nodes rakho magar zyada edges hata do taa ke cycle na bane.
Connected Network: You can reach any node from any other node by following a path. The network is in one piece.
Tree: A connected network that has no cycles. It's the simplest way to connect all nodes without redundancy.
Spanning Tree: A tree that includes all the nodes of the original network. It's a minimal way to connect everything.
Direction ka kya role hai?
Directed arcs woh hote hain jo sirf ek hi direction mein flow allow kartay hain. (Jaise aik taraf chalne wali sadak)
Directed network woh hota hai jismein har arc ka ek specific direction hota hai.
Paths aur Cycles kya hotay hain?
Path: Aik aise route ka naam hai jo kisi bhi node se doosri node tak jata hai.
Example: 1 → 3 → 4 → 2
Cycle: Jab aik path ghoom phir ke waapas ussi node par aa jaye jahan se shuru hua tha.
Example: 2 → 3 → 4 → 2
Connected Networks, Trees, aur Spanning Trees
Connected network: Aisa network jismein har node doosri nodes se kisi na kisi path ke zariye connected ho.
Tree: Aik aisa connected network jismein koi cycle (loop) nahi hoti.
Spanning Tree: Aik tree jo poore network ke saray nodes ko cover karta ho, lekin koi extra loop na ho.
Example
Agar aik network mein 5 nodes hain aur hum sirf kuch arcs rakh kar sab nodes ko bina kisi extra loop ke jod dain, toh woh spanning tree hoga.
Aakhri Baat
Yeh concepts real life mein bohat kaam atay hain, jaise:
Shortest route find karna
Internet ya electricity network design karna
Traffic control system banana
Bridges of Königsberg ka masla ek mashhoor riyazi (mathematical) masla hai jo Graph Theory ki bunyad par mabni hai. Yeh masla Königsberg shehar mein paaya gaya tha, jo ab Russia ka hissa hai aur Kaliningrad ke naam se jana jata hai. Is shehar mein ek darya ke sath do jazeere thay aur in jazeeron aur darya ke kinare ko milane ke liye 7 pul (bridges) thay. Masla yeh tha ke kya koi aisa rasta hai jisse har pul ko sirf ek hi martaba cross karke poori shehar ka safar kiya ja sake? Kya koi aisa tareeka hai ke hum har pul se guzrein bina kisi pul ko dobarah cross kiye?
Is masle ko Leonhard Euler ne 1735 mein hal kiya. Euler ne is masle ko hal karne ke liye Graph Theory ka istemal kiya. Usne shehar ke hisson (yani zameen ke tukdon) ko nuqat (nodes) aur pulon ko khat (edges) se zahir kiya. Euler ne yeh qaidah diya ke agar har nuqte (node) par pulon ki tadad juz (odd) hai, to aisa safar mumkin nahi hai. Lekin agar sirf do nuqton par pulon ki tadad juz (odd) hai, to aisa safar mumkin hai, lekin shuru aur khatam alag-alag nuqton par hoga. Königsberg ke masle mein, charo nuqton par pulon ki tadad juz thi, isliye Euler ne sabit kiya ke yeh masla hal nahi ho sakta.
Is masle ne Graph Theory ki bunyad rakhi, jo aaj computer science, networking, aur planning mein bahut ahmiyat rakhta hai. Yeh masla humein yeh samajhne mein madad deta hai ke kaise hum raston, connections, aur resources ko behtar tareeqe se istemal kar sakte hain. Misal ke tor par, agar aapke ghar ke bahar teen raste hain aur aap har raste ko sirf ek hi martaba istemal karke ghar wapas aana chahte hain, to agar kisi bhi crossing par raston ki tadad juz hogi, to aisa karna mumkin nahi hoga. Königsberg ka masla bhi kuch isi tarah ka tha.
Disclaimer:The educational content provided on this website has been sourced from publicly available resources. We do not claim ownership of any third-party material used on this site. All trademarks, images, and content are the property of their respective owners. If you believe any content on this site infringes upon your copyright or intellectual property rights, please contact us, and we will take appropriate action.
